Generally speaking, most JavaScript array search algorithms I see in production code look something like this:

```
var myArray = [ 1, 2, 3, 4 ],
key = 3;
function linearSearch (key, inputArray) {
var i;
for (i = 0; i < inputArray.length; i++) {
if (key === inputArray[i]) { return i; }
}
return null;
}
linearSearch(key, myArray); //returns 2
```

This is a classic **linear search algorithm**: we loop through a given array checking to see if a key exists. The search starts at one end of the array (usually the beginning) and incrementally moves toward the opposite end, returning the index of the key (if it exists). In most cases, the input array is not sorted.

The linear search algorithm is often "good enough" for most applications. Although optimization would improve performance, the benefit might only be minimal if our data set (stored in an array) is relatively small.

The linear search algorithm (represented in the above code sample as the *linearSearch()* method) takes two input parameters:

- key (an integer)
- inputArray (an array of integers, not necessarily sorted)

This algorithm returns:

- the index of the key (if present), or
- null

But what happens to our algorithm as the data set increases in size?

### Measuring Search Efficiency

When we study the structure of algorithms, we represent the growth rate using Big-O Notation. In short, Big-O Notation is a mathematical forumla that demonstrates how a function performs as its inputs (or memory requirements) change.

In practice, Big-O Notation represents the mathematical limit (i.e. upper-bound, or ceiling) for performance given some input. **It is the worst-case scenario for the algorithm.**

For example, the Big-O Notation for the linear search algorithm is **O(n)** - where **n** is the size of the array we're searching. This means that for an array containing 10 elements, the linear search will take *at most* 10 loops through the data set. For an array containing 10,000 elements, linear search will take *at most* 10,000 loops.

If you were to plot these on graph paper, you would see the growth of maximum execution is linear - appropriate considering the name "linear search". In a production environment, linear search often performs better than O(n) because we rarely have to look at each array index every time the algorithm is executed.

However, we should never assume our algorithms will not hit their limits in production. The whole point of measuring Big-O Notation is to mathematically compare options.

In the case of linear search, we probably want to consider a more efficient option if one is available.

### Binary Search

The **Binary Search** algorithm takes a divide-and-conquer approach. Given a sorted array (a key difference from linear search), the algorithm checks the key against the middle index value of the array. The algorithm then continuously divides itself until it finds the correct index (if it exists).

The binary search algorithm takes two inputs:

- key (an integer)

- inputArray (a *sorted* array of integers)

This algorithm returns:

- the index of the key (if present), or

- null

```
function binarySearch(key, inputArray) {
var low = 0,
high = inputArray.length - 1,
mid;
while (low <= high) {
mid = low + (high - low) / 2;
if ((mid % 1) > 0) { mid = Math.ceil(mid); }
if (key < inputArray[mid]) { high = mid - 1; }
else if (key > inputArray[mid]) { low = mid + 1; }
else { return mid; }
}
return null;
}
// run the binary search
binarySearch(3, [1,2,4]); //returns null
binarySearch(3, [2,3,5]); //returns 1
```

Binary search will **never** have to loop through every index in the array. In fact, the growth of maximum execution (i.e. worst case scenario) is **O(log n)**. For those of you who don't remember high-school math, logarithmic growth is exponential... but in this case, the growth is far less compared to it's linear option.

### Comparing Linear and Binary Search

Keeping in mind that Big-O notation is the worst case scenario, we can expect the following results*:

Array Size | Linear: O(n) | Binary O(log n) |
---|---|---|

10 | 10 | 2.30 |

100 | 100 | 4.60 |

1,000 | 1,000 | 6.90 |

**These results are not actual times... just the maximum number of iterations in the algorithm*

Do you see a pattern here? While these numbers represent the worst-case scenario (and algorithms do not consistently perform at their worst), they're obviously important to consider. This is particularly true when your data sets grow larger.

### For Example...

I put together a short example comparing the expected (worst-case) and actual performance of these two search algorithms. To level the playing field, both algorithms will use the same key (randomly generated) and the same input array (which is sorted).

If you keep hitting the "run" button, you'll see that the actual performance of each algorithm changes as the new (random) key is generated. Although linear search is *sometimes* more efficient on smaller data sets, you will notice that binary search is *consistently* better on larger data sets.

In fact, my example seems to indicate that sorted arrays with more than 10 elements *almost always* perform better than linear search. In other words, with the exception of infrequent and rare circumstances, binary search is clearly the better choice.

### What do you think?

Is my logic flawed? Is binary search a realistic option for production programs?

Your thoughts and comments are definitely welcome!

I actually had this conversation with my mentor one time- he was talking about programming & search functions in large data sets.

For larger data sets the Binary advantage in its search has to be offset against time spent auto-sorting the data as step 1.