A brief explanation
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 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.
Against an array of 10,000 records indexOf and includes out performed our Binary Search. Here is how they all performed:
includes took 0.009970879554748536 milliseconds
indexOf took 0.01036243438720703 milliseconds
Binary Search took 0.02087087631225586 milliseconds
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).
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.
Binary Search took 0.006424903869628906 milliseconds
includes took 0.008549976348876952 milliseconds
indexOf took 0.009720849990844726 milliseconds
findIndex took 0.1365041732788086 milliseconds
find took 0.13874146938323975 milliseconds
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.