Binary Search

Big O

If we were put this optimization in Big O terms we would say that we are reducing our worst case run time from O(n) to O(log n). A basic traversal could potentially require the iteration of every single element. Therefore the run time is increasing proportionally to the number of elements. With binary search the number of remaining elements is continually being halved so this is described as log2 n (logarithm to the power of 2), which is more commonly just referred to as “log n” in programming. This is basically the inverse of exponential growth.

Implementation

Here’s how we would implement binary search on an array in Javascript. First we would need to create 3 pointers. One at the beginning of the array, one at the end of the array, and one in the middle. The middle element can be calculated by adding the beginning and end pointers, dividing the sum by 2 and then using the Math.floor function to round the number down to the nearest integer.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store