Skip to main content

Linear Search

Definition:​

Linear search, also known as sequential search, is the simplest searching algorithm. It checks every element in the array (or list) one by one until the target element is found or the entire array has been searched. The algorithm doesn't assume any particular order in the data and is useful for small or unsorted datasets.

Characteristics:​

  • Sequential Search:

    • The algorithm traverses the array one element at a time, comparing each element with the target value.

  • Unordered Data:

    • Linear search works on any dataset, whether sorted or unsorted, making it a versatile search method.

  • Simplicity:

    • Linear search is one of the easiest search algorithms to understand and implement. It requires no preprocessing or complex data structures.

  • Inefficient for Large Data:

    • The algorithm is inefficient for large datasets because it potentially searches through every element, making it slow in comparison to more advanced search techniques.

  • Works with All Data Types:

    • Linear search can be applied to any data type that supports comparison, making it universally applicable.

Time Complexity:​

  • Best Case: O(1)O(1)
    In the best case, the target element is found at the very beginning of the array, requiring only a single comparison.

  • Average Case: O(n)O(n)
    On average, the algorithm must search through half of the elements in the array before finding the target.

  • Worst Case: O(n)O(n)
    In the worst case, the target element is located at the end of the array, or it may not be present at all, requiring a full traversal of the array.

Space Complexity:​

  • Space Complexity: O(1)O(1)
    Linear search requires a constant amount of additional memory, regardless of the size of the array, making it a space-efficient algorithm.

  • Unsorted or Small Data:

    • Linear search is ideal for small or unsorted datasets where more complex algorithms may not offer significant performance improvements.

  • Checking Every Element:

    • It is useful when every element needs to be checked regardless of whether the data is sorted or not, such as searching for a specific condition.

  • Data in Linked Lists:

    • Linear search works well with linked lists, where random access is not possible and each element must be checked sequentially.

C++ and Python Implementation:​

Iterative Approach

#include <iostream>
using namespace std;

int linearSearchIterative(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Return index if target is found
        }
    }
    return -1; // Return -1 if target is not found
}

int main() {
    int arr[] = {10, 23, 45, 70, 11, 15};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 70;

    int result = linearSearchIterative(arr, size, target);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}
def linearSearchIterative(array, size, target):
    for i in range(len(array)):
        if array[i] == target: 
            return i #Return index if target is found
    return -1 #Return -1 if target is not found
def main():
    array = [1 ,2 ,5 ,3 ,7 ,9 ,4 ,1 ,9 ,6 ]
    size = len(array)
    target = 9
    result = linearSearchIterative(array,size,target)
    if result != -1:
        print("Element found at index",result)
    else:
        print("Element not found ")

if __name__ == "__main__":
    main()

Recursive Approach

#include <iostream>
using namespace std;

int linearSearchRecursive(int arr[], int size, int target) {
    if (size == 0) {
        return -1; // Return -1 if the array is empty
    }
    if (arr[size - 1] == target) {
        return size - 1; // Return index if target is found
    }
    return linearSearchRecursive(arr, size - 1, target); // Recur for the rest of the array
}

int main() {
    int arr[] = {10, 23, 45, 70, 11, 15};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 70;

    int result = linearSearchRecursive(arr, size, target);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}
def linear_search_recursive(arr, size, target):
    if size == 0:
        return -1  # Return -1 if the array is empty
    if arr[size - 1] == target:
        return size - 1  # Return index if target is found
    return linear_search_recursive(arr, size - 1, target)  # Recur for the rest of the array

def main():
    arr = [10, 23, 45, 70, 11, 15]
    size = len(arr)
    target = 70

    result = linear_search_recursive(arr, size, target)

    if result != -1:
        print("Element found at index", result)
    else:
        print("Element not found")

if __name__ == "__main__":
    main()

Use Cases:​

  • Looking for a Specific Value:

    • Linear search is often used when you want to find the index of a specific value in an array or list, especially when the dataset is small or unsorted.

  • Finding a Minimum or Maximum:

    • Linear search can also be used to find the minimum or maximum value in an unsorted array by comparing each element with the current minimum or maximum as you traverse the list.

  • Linked Lists:

    • Since linked lists don't allow random access to elements, linear search is the go-to search method for finding values in a linked list structure.

Advantages and Disadvantages:​

Advantages:​

  • Simplicity:

    • Easy to implement and understand, making it ideal for quick searches in small datasets or educational purposes.

  • No Preprocessing:

    • Linear search doesn't require any preprocessing like sorting or indexing, making it applicable to any kind of data.

  • Universal Application:

    • Works with any data type that supports comparison, whether it's numbers, strings, or complex objects.

Disadvantages:​

  • Slow for Large Datasets:

    • Linear search is inefficient for large datasets, as it has to examine each element until it finds the target.

  • No Optimization:

    • It doesn't take advantage of the structure of the data, such as order or indexing, which could be exploited by more advanced algorithms like binary search.

  • Not Ideal for Sorted Data:

    • If the data is sorted, more efficient algorithms like binary search should be used instead of linear search.

Optimization:​

  • Sentinel Search:
    • A slight variation of linear search called the sentinel search can be used to reduce the number of comparisons. By placing the target element at the end of the array as a "sentinel," the search loop can eliminate the need to check if the array is fully traversed in each iteration.
int sentinelSearch(int arr[], int size, int target) {
    int last = arr[size - 1]; // Store the last element
    arr[size - 1] = target;   // Set sentinel
    
    int i = 0;
    while (arr[i] != target) {
        i++;
    }
    
    arr[size - 1] = last;     // Restore the last element
    
    if (i < size - 1 || arr[size - 1] == target) {
        return i;
    } else {
        return -1;
    }
}

Summary:​

Linear search is the most basic and straightforward search algorithm, making it suitable for small or unsorted datasets. Its simplicity is its greatest strength, but its inefficiency for larger datasets is a major drawback. While it's not the most optimal choice for sorted or large data, it remains an essential algorithm for scenarios where simplicity or sequential checking is required. Though linear search has a time complexity of O(n), it can be implemented with constant space, making it useful for memory-constrained environments.