Binary Search vs indexOf
A look into binary search vs indexOf, with benchmarks to compare the performance differences
The more data we have the more performant we want or need our searches to be for a particular piece of that data. In a worst case scenario, we don’t want our application to be slow because of an inefficient lookup. Lets first look at the simplest form of a search, indexOf, and then move onto binary searches and how they are implemented.
indexOf
indexOf() may be your first choice when trying to find an element in an array. It’s part of native JavaScript so will be the easiest/quickest to implement. However, it may not be the best choice to use this if you have an array of 100,000 elements.
indexOf() is a linear search, meaning it starts at the very first element in the array and iterates over the rest, one element at a time, until it finds what it’s looking for. This method runs in O(n) time, where n is the length of the array.
Binary Search
Binary searches cut out a lot of time by using mid points within an array. It works by comparing the search value with a middle element of an array. If the search value is greater, all the elements to the right of that initial mid point are used to do a second search. A new mid point is then calculated from the right set of elements. The process continues until the search value is found. This has a complexity of O(log n). (Side note: I have referenced Big O Notation a couple times, so if you would like to learn more about this topic these are great resources: HackerRank video and Hackernoon article).
The gif below is a perfect visualisation of how this works compared to a linear search:
Now you may have already noticed that binary searches can only be used on sorted arrays. This is a potential drawback. If you’re only planning on doing a single search on an unsorted array then it is not worth using binary search. The extra operation of sorting the data first will take much longer than just doing a linear search on the unsorted array. Another con is that it is much slower with smaller data sets as shown in the examples below.
Benchmarks
For each of the test cases below I used a site called JSBench.Me. All code put in setup gets run before any of the test case code.
Setup
Firstly I created a binarySearch function:
Next I needed to generate a load of data to search through:
Now some test cases can be added. Note for each test case I also alter the setup slightly.
Test case 1: Large sorted data set (100,000 elements)
For this test case I first added a couple things to the setup:
array.sort((a, b) => a > b ? 1 : -1)
let findEl = array[getRandomNumber()]The findEl variable ensures that both methods are looking for the same element making it a fair comparison. Results:
As you can see the binary search is considerably faster (99.98% faster in this case).
Test case 2: Small sorted data set (100 elements)
As in the previous test case, array.sort() and the findEl variable are added to the setup. This time, however, I am only putting 100 elements in the array. Results:
In this case it would just be easier to use indexOf().
Test case 3: Large unsorted data set (100,000 elements)
For this case I moved the array.sort() out of the setup and included it in the binarySearch() test case. This test just shows that if you want to do just one search, it’s not worth sorting the array right before using binary search. Results:
Conclusion
Whether you use a binary search or indexOf will depend entirely on how your data is arranged, what you’re trying to achieve, and if performance even needs to be considered. If you have a huge sorted data set, binary search could be an option. If there’s a small amount of data, indexOf may be easier/better to implement. If you have a lot of data but it’s unsorted and you’re only doing one search, you may be better off just using indexOf. Hopefully this has given a bit of an insight into the pros and cons of each method. Thanks for reading!