Linear Search
A linear search is the most basic of search algorithm you can have. A linear search sequentially moves through your collection (or data structure) looking for a matching value.
Implementation
function findIndex(values, target) {
for(var i = 0; i < values.length; ++i){
if (values[i] == target) { return i; }
}
return -1;
}
findIndex([7, 3, 6, 1, 0], 6)
Example
Click step to step through the above implementation and find 6 within the following list
Characteristics
The worst case performance scenario for a linear search is that it needs to loop through the entire collection; either because the item is the last one, or because the item isn't found. In other words, if you have N items in your collection, the worst case scenario to find an item is N iterations. This is known as O(N) using the Big O Notation. The speed of search grows linearly with the number of items within your collection.
Linear searches don't require the collection to be sorted.
In some cases, you'll know ahead of time that some items will be disproportionally searched for. In such situations, frequently requested items can be kept at the start of the collection. This can result in exceptional performance, regardless of size, for these frequently requested items.
In The Real World
Despite its less than stellar performance, linear searching is extremely common. Many of the built-in methods that you are familiar with, like ruby's find_index, or much of jQuery, rely on linear searches. When you are dealing with a relatively small set of data, it's often good enough (and for really small unordered data is can even be faster than alternatives).
Beyond this though, the general concept of sequential/linear access is something that is often overlooked. The more abstract libraries get, the more risk you run of unknowingly doing something linearly. .NET's LINQ is a great example. Most of LINQ works against IEnumerable<T> which only exposes a forward moving enumerator. So what do you think happens when you call the Count() method? Thankfully, LINQ is smart and, if possible, it'll rely on a fast Count or Length property. However, if the actual implementation doesn't have those, it'll loop through the enumerator.
That doesn't make LINQ's Any, or Ruby's include? "evil". It's just good to know what these high level methods might be doing (and often, what they are doing, is a linear search).