Performing Binary Search in JavaScript and Ruby

Binary Search is arguably the most effective means of searching through very large data to find a target value. It does by eliminating half of the data each time it traverses through to find the target. For example, if you were to search through 1–20 to find 11, how would you do that? the first reaction would be to search linearly by counting from 1 till you find 11, you won’t notice how tasking this can be until you are searching for 1,123,000 out of 2,000,000 numbers but you can greatly simplify this process using binary search. If we are to find 11 from 1–20 using binary search, all we have to do is get the value in the middle i.e. 10 and we compare with 10 with our target value, since 11 is greater than 10, we then eliminate every value from 10 downwards, then we get the middle value once again between 10–20 i.e. 15 then compare with 11, now 11 is less than 15, so in the case, we eliminate all values from 15 upwards, we keep repeating this step until we find the target value. Again, since the dataset (1–20) is small, we may not notice how time and effort saving binary search can be until you search a very large set of data.

Binary search becomes more effective with increase in data. For instance, we would require a lot less steps while searching for 1,123,000 among 2,000,000 numbers compared to linear search than we would search for 11 among 20 numbers. Let’s run a pseudocode to see how many steps it will take us to search for 19 among 30 numbers;

• First, we set our default min and max values to 0 and array.length i.e. 29 respectively.

min = 0
max = 29

• Get the average of the min and max values and set it to a variable of your choice, let’s call ours search. Remember to round search to the nearest whole number.

search = (0+29)/2 = 14.5 ~ 15

• Compare search to the target value 19, if search = 19, then we have found our answer, if not, we can proceed. In this case, search is not equal to 19.

if search == targetValue
    return search

• If search is less than targetValue, we set min = search + 1. Since search, 15, is less than targetValue, 19, we set our min = 15+1=16.

if search < targetValue
    min = search + 1

• Next, we recalculate our search variable, i.e. (16+29)/2 = 45/2 = 22.5 ~ 23. Remember, we always round off search.

search = (16+29)/2 = 22.5 ~ 23

• Compare search to target value once again, as before, if search == target value, we simply return search. In this case, search is greater than the target value.

if search == targetValue
    return search

• If search is greater than targetValue, we set max = search -1. i.e. max = 23–1=22.

if search > targetValue
   max = search - 1

• Once again, we recalculate our search value, i.e. (16+22)/2 = 38/2 = 19.

search = (16+22)/2 = 38/2 = 19

• Compare search to target value once again, as usual, if search==targetValue, we have found our answer. Here, search == target meaning, we found our answer! So we return search.
• Lastly, if none of the above conditions are met, we set the function to return -1.

It took us 9 steps to search for our target value among 30 numbers, if we were to count linearly, it will take about 19 steps to do the same, so now you can see how effective Binary search is.

Now, we are going to translate our pseudocode into real-life code in JavaScript and Ruby so we can better appreciate Binary search:

Ruby Implementation

JavaScript

Conclusion

One very important thing to note about performing a Binary search is that you slice the array in half each time you perform a search. In our code above, we made an iterative solution for solving Binary search, you could also solve the problem using recursion if you want to. The true power of binary search lies when you have millions probably billions of elements to search through, it is also a widely used method for search in Computing.