Linear Search

Linear search is a simple search algorithm that searches for a target value in a list. It compares each element of the list to the target value until it finds a match or until all elements have been searched.

Implementation

Pseudocode

procedure linearSearch(A : list of items, target : item)
    for i = 0 to length(A) - 1 do
        if A[i] = target then
            return i
        end if
    end for
    return -1
end procedure

Java

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

Runtime Analysis

Given $N$ elements in the list, the time complexity of linear search is $\Theta (N)$.

Best Case

The best case occurs when the target value is found at the first position in the list. The time complexity is $\Omega (1)$.

Worst Case

The worst case occurs when the target value is not present in the list or is found at the last position in the list. In this case, the algorithm makes $N$ comparisons. The time complexity is $O(N)$.

Source

The existing course note was retained and normalized during the merge.

Related: Topic index.