Intro

I just want to preface this article with an admission that I do not have a degree in computer science. I'm educating myself on search algorithms through online research, and trial and error. What you'll read below are my findings and tests (working in JavaScript).

Binary Search

Binary Search is an algorithm for searching through sorted arrays. It works for arrays of numbers and strings. When an array contains strings the comparison is based on lexicographic (the lexical order).

How does it work

Binary Search works by repeatedly dividing the search interval in half.

So what does that mean?

It means choosing the middle value of an array and checking if it matches a target value. If it does, return the array index. If it doesn't, half the array and repeat the search.

When compared to linear search, which checks every element in an array from the beginning, you can see the benefit of Binary Search. If the target value were the last element in an array of 16 elements, it would take 16 guesses. With Binary Search, it would take 4 guesses.

Binary Search shines with very large data sets. So on smaller arrays, linear search can be a good choice. More on that later.

The Math

When looking at algorithms, we measure their efficiency based on time complexity and use the Big O Notation to show how that looks as their run time or space requirements grow.

When finding the target value on the first guess, Binary Search has a best case scenario of 0(1).

If finding the target value on the last guess Binary Search has a worst-case scenario of O(log N).

Tests

To see how efficient Binary Search is compared to linear search functions I tested it using an array of prime numbers, running the Binary Search 10 times and getting the average time to find the predicate term. The predicate term is the last item and will always be the last in the array in these tests.

Here is the Binary Search method I wrote in JavaScript to run these tests.

The JavaScript methods I also tested on the same datasets were findIndex, indexOf, includes and find.

10,000 records

Against an array of 10,000 records indexOf and includes out performed our Binary Search. Here is how they all performed:

1. includes took 0.009970879554748536 milliseconds

2. indexOf took 0.01036243438720703 milliseconds

3. Binary Search took 0.02087087631225586 milliseconds

4. find took 0.14579181671142577 milliseconds

5. findIndex took 0.17606682777404786 milliseconds

So here we can see that Binary Search is slower than includes and indexOf. This is odd because they both need to make 10,000 searches to find the last element, whereas the Binary Search only needs to make 13 guesses (log2(13) = 10000).

The only reason I can find for this is that the JavaScript V8 Engine is written in a low-level language which will increase their performance. Still, we know that Binary Search works best on larger datasets, so let's test again.

100,000 records

That's a lot of prime numbers now, and unsurprisingly, Binary Search pulls away from the pack. The predicate is again the very last item in the array. Here is how the same methods performed again.

1. Binary Search took 0.006424903869628906 milliseconds

2. includes took 0.008549976348876952 milliseconds

3. indexOf took 0.009720849990844726 milliseconds

4. findIndex took 0.1365041732788086 milliseconds

5. find took 0.13874146938323975 milliseconds

The JavaScript methods each take 100,000 guesses to reach the target value, whereas the Binary Search reaches the value in no more than 16 guesses (log2(16) = 100000).

The Take away

Binary Search is a really useful algorithm when working on large sets of data in an ordered list. If you have a large sorted array, use Binary Search.

If your data is unordered you could order it and then use Binary Search, but that would accumulate more time being spent ordering your array before even starting the search.

So in the case of an unordered list or a small data set, you'll get better peformance using the language array methods includes or indexOf.