Binary Search in JavaScript
If you are new to Binary Search, I suggest you read my previous blog post “Algorithm Series — Binary Search”, before reading this article.
Coding Task
Implement Binary Search on the array [2, 5, 6, 9, 13, 15, 28, 30] in order to find the value 15.
Pseudocode
For Binary Search to work, we need to have a sorted array. Sorted means, that it is ordered — this can be applied to strings also (A < B < C), not only numbers. The array in our task is sorted from lowest to highest, so this prerequisite is met. Within our array, we have to create three pointers: A left pointer at the start, a right pointer at the end, and a middle pointer at the middle (duh). In edge cases (like when we are looking for a value that is not in the array), it may happen that the pointers cross over (more on that later), which would lead to undesirable outcomes like infinite loops. So what we do is this:
While the left pointer comes prior to the right pointer…
- Create a middle pointer (take the average of the index)
- If you find the value, return the index
- If the value is less than the value in the middle, move the right pointer down
- If the value is greater than the value in the middle, move the left pointer up
- If you never find the value, return -1
Code Implementation
We are working with indices. The start (left pointer) is index 0, the end (right pointer) is index 7. Length equals the number of values in our array, which is 8 — but there is no 8th index (because they start at 0). The last value in our array is 30, which is in index 7, so we deduct 1 from our array length to get the proper index for the end. The middle of 7 = 3.5, and we obviously don’t have a value in index 3.5. In our implementation we decided to round down with Math.floor but it is perfectly fine to round up with Math.ceil. The only important thing here is to be consistent with what one decides to choose. Since we rounded down, our middle point is index = 3, which equals value 9.
In the while condition, we check whether the value at the middle index equals the element we are looking for, which is 15. While the value at the middle index doesn’t equal the value we are looking for, we check whether the element we are looking for is less than the value at the middle index. If it is, we shift the end point one index left to the middle, and if it is not (if the value we are looking for is greater than the value at the middle index), we shift the start point one index right to the middle. Subsequently, we calculate a new middle point. Our check…
while(arr[middle] !== elem)… equals true on our initial SME, because the value we are looking for is not equal to the value that is at the middle index.
Then we either need a new start index (if the value we are looking for is greater than the middle point) or a new end index (if the value we are looking for is less than the middle point). Since we are looking for 15 we fall into the else block:
else {
start = middle + 1;
}Here, we are setting a new start point. Afterwards…
middle = Math.floor((start + end) / 2);
…we create a new middle point, which is not bound to the if-else, because if the value we are searching for wasn’t at our initial middle index (so if the while statement equals true), we will have to create a new middle point regardless of whether the value we are looking for is greater or less than the value at the middle point. Why is 15 the middle point? Remember, we are working with indices. The new start index is 4 (value 13) and the end index is still 7 (value 30). The indices added up equal 11 and the middle of 11 is 5.5. Since we were rounding down at the beginning, our continued practice gives us a middle point of 5, where the number 15 is. And that is the number we were looking for. We found it! Let’s make it a bit trickier and search for the number 28. How would the next iteration look like?
If you predicted that correctly, congratulations! If not, remember:
else {
start = middle + 1;
}The start point gets reset and equals now the middle point + 1 (which is value 28). The middle equals the middle index (duh) of the start point plus the index of the end point, which is index 6 + index 7 = 13. The middle of index 13 is 6.5 and we round it down to 6, which equals value 28. So now, the start and the middle point are at the same spot, while the end point hasn’t moved. And we found our value! Let’s test our code:
There is one big problem with our code though: It doesn’t really work. Meaning, it doesn’t work with a certain edge case — if we search for a value that is not in the array, what happens?
After the second iteration, the new starting point is the middle point + 1, which is index 7. So the start point and the end point are both index 7 then and if we add both indices and halve the result, we get a new middle point of index 7. The third iteration then, will locate all points — start, middle and end — on 30. But since we still haven’t found 50, we iterate again. Now though, the start index is 8, which is out of bounds. The start point has eclipsed the end point, it has crossed over. The middle point doesn’t move, since index 8 + 7 = 15 and divided by two and rounded down we still get 7. During the next loop, the start point gets set equal to the middle point + 1, which is still 8. This means, that all our points are stuck and won’t move. We are in an infinite loop we have to get out of.
while(arr[middle] !== elem) && start <= end)Now, we implemented a way to get out of the infinite loop. We stated another condition, which has to evaluate to true for the while loop to run. When our start point eclipses our end point, the while loop stops running and the function returns the middle index:
Hooray! There are good and bad news: Although we managed to get out of the infinite loop, we return the wrong index! This is easily solvable though, with an additional line of code:
On the last line, we are saying “if the value at the index of the middle point in the array equals the element, return the middle index, otherwise return -1.”
Hope this was clear :) if you have any questions, don’t be shy to ask! (:
