A brief explanation

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 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).

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.

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)*.

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.

Against an array of 10,000 records * indexOf* and

**includes**took 0.009970879554748536 milliseconds**indexOf**took 0.01036243438720703 millisecondstook 0.02087087631225586 milliseconds**Binary Search****find**took 0.14579181671142577 milliseconds**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.

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.

took 0.006424903869628906 milliseconds__Binary Search__**includes**took 0.008549976348876952 milliseconds**indexOf**took 0.009720849990844726 milliseconds**findIndex**took 0.1365041732788086 milliseconds**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)*.

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