We are asking browsers to do more and more as they become more capable. I’m not sure if that’s a good thing or not, but that’s a heated flame war that should be saved for another day.
There may come a time in your browser (ab)use in which you need to search a ridiculous amount or values within a cat gif processing platform. Or maybe you need to search through all of the elements in a bloated DOM.
You will probably find that
This is where you have an excuse to suggest a binary search and blow everyone else’s minds.
What is it
A binary search searches by splitting your array into smaller and smaller chunks until it finds your desired value. Unlike the normal
indexOf which searches from left to right in a simple iteration. The binary search Wikipedia article explains it best (as always). There are a couple of downsides; It will be slower with smaller data sets (this needs proving) and the array you are searching needs to be sorted.
Because a binary search is O(log n), and not O(n) like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
Real world use case
Say we have a
Model class that each have a numerical ID or publish time. The first thing you would need to do is sort them. You can either do this with a sorting function like this…
1 2 3
Or you can do it the smart way which kills two birds with one stone. You define a
valueOf method which returns the ID. This value can then be used by the default sort method and, more importantly, within the
binaryIndexOf method which needs the comparison operators to work correctly in order to find things.
1 2 3 4 5
So now that your models are sorted and their greater than and less than comparison operators will work, you can use the
binaryIndexOf method on it to search through your 100,000 models. Why are you even doing this to a browser, you monster.
1 2 3 4 5 6
Let me know what you think and if you have any improvements or suggestions. I hope this can help to destroy a bottleneck or two (or 100,000).
Edit: Where should you stick it?
doomslice over on reddit suggested that I return the twos compliment in place of -1. As far as I can tell, this means returning the negative version of the last place that was checked. So if you wanted to insert a value and wanted to know where you should put it, you could run the function and use the returned number to splice the value into the array.
This way you can add items without ruining the order. You don’t exactly want to go re-sorting potentially thousands of values every time you add something. Here’s the modified function I came up with, as well as a working example. It demonstrates finding where to insert an element and then inserting it.
As you can see, because I use the bitwise NOT operator (
~, also suggested by doomsice!) on the index during the splice, it will always insert the element in the right place, even if there is an identical value already there! Pretty cool. You do have to be careful though, now you are going to need to check for
index < 0, and not
index === -1 when you are looking for existence of a value.