Linear search

Check every element in order until the target turns up. The only search that works on unsorted data.

Time O(n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

There is no trick here. Walk the array from index 0 and compare each value with the target. Stop at the first match.

Code

C++PythonC#

int linearSearch(const vector<int>& a, int target) {
    for (int i = 0; i < (int)a.size(); i++) {
        if (a[i] == target)
            return i;
    }
    return -1;
}

def linear_search(a: list[int], target: int) -> int:
    for i in range(len(a)):
        if a[i] == target:
            return i
    return -1

public static int LinearSearch(int[] a, int target) {
    for (int i = 0; i < a.Length; i++) {
        if (a[i] == target)
            return i;
    }
    return -1;
}

Tips

Best case is 1 comparison, worst case is n.
If you search the same data many times, sort it once or load it into a HashSet.

In the .NET library

Array.IndexOf(a, target) and List<T>.Contains run exactly this scan.