Linear Search

Task: Find 23 in this unsorted array

int indexOf(int[] a, int target) {    for (int i = 0; i < a.length; i++) {        if (a[i] == target) {            return i;        }    }    return -1;   // not in the array}

What you are watching

Linear search checks each value in turn until it finds the one it wants or runs out of array. It makes no assumptions at all: the values here are in no particular order, which is exactly the situation binary search cannot handle. Looking for 23, which sits at the very last index, costs all eight comparisons - the worst case, and the one that gives linear search its O(n) bound. A value at the front would have cost one.