Linear Search

“Linear Search” is a basic algorithm: How do I find something in an array of things?

Template for Linear Search

for each element of the array:
    Is this the element I’m looking for?
        If yes, return the location
    Otherwise, continue with the next element

Finding the Largest Element

Linear search can also be used to find items with some property or to find the largest or smallest thing.

Here’s a template for finding the smallest thing:

Analysis

How many steps does it take to find something with linear search?

In general, we have to step through each element of the array. Even if we’re searching for things at arbitrary locations, we can expect to search half the array.

If we search the whole array, we loop array.length times. The cost of each iteration depends on many factors, but at least we can say the cost is proportional to the length of the array. Sometimes we write this O(array.length). Often, we use the variable N to mean “the size of the problem”, in this case, the size of the array, so the cost of the search is O(N). (Pronounced either “Order N” or “Big-Oh of N”).

If we search half the array, we loop array.length/2 times. The cost of each iteration depends on many factors, and we have a factor of 1/2 as well, but at least we can say the cost is (again) proportional to the length of the array. Thus, this also costs O(array.length) or O(N).

Bottom line: Linear Search is an O(N) algorithm.

Are there faster ways to search? How does Google work?