“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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
function searchArrayForSomething(anArray, something) { for (var i = 0; i < anArray.length; i++) { if (anArray[i] == something) { return i; // the location of something } } return -1; // something was not found } // here's how it might be used: var locationOfSomething = searchArrayForSomething(myArray, x); if (locationOfSomething > -1) { println("I found " + something + " at index " + locationOfSomething); } |

## 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
function smallest(anArray) { // start with a candidate smallest item var smallestVal = anArray[0]; // and it's location var indexOfSmallest = 0; // then search to see if anything is smaller for (var i = 0; i < anArray.length; i++) { if (anArray[i] < smallestVal) { // found something smaller, remember the smallest so far: smallestVal = anArray[i]; indexOfSmallest = i; } } return indexOfSmallest; } // here's how to use the function var loc = smallest(myArray); println("The smallest value, " + myArray[loc] + " is at location " + loc); |

## 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?