Binary Search Algorithm: An Introduction

Algorithms are a set of rules or process used to solve a problem. The ‘problem’ can be needing to encrypt text, needing to search through a collection of data for values matching a certain input, sorting through a collection of data and ordering by a certain parameter, and so on.

One of the faster options for a searching algorithm is the Binary Search. As opposed to a linear search (which compares the value you are searching for to each item in the collection, thus having a run-time complexity of O(n)), Binary Search has a run-time complexity of O(log n) and is based on the principle of divide-and-conquer. In order for this approach to function as desired, the data collection needs to be sorted.

Binary Search functions by comparing the middle most item of the collection to the particular value the algorithm is searching for. The index of that item is returned if a match occurs. If this does not occur, the item is searched for in the sub-collection to the left of the middle item if the item is less than the value of middle item, or in the sub-collection to the right if it is greater. The collection is divided based upon this information and the middle item of this new sub-collection is compared to the sought after item. This continues until a match occurs, decreasing the size of the collection by half each time until the sub-collection is reduced to zero. As you can likely surmise from this summation of Binary Search, a sorted data collection is imperative for the proper functioning of this divide-and-conquer style algorithm.

Pseudocode Example

One of the most common applications of Binary Search is in finding a value within a sorted array. As such, we will start with a sorted array of numeric values —

[2, 4, 6, 9, 22, 77, 100]

The first step in Binary Search is to determine the middle item of the collection with this formula:

middle = lowIndex + ((highIndex - lowIndex) / 2)

Remember that our index starts at 0, so we have an index range of 0 to 6 in our example array. So with our example array, this formula would be —

middle = 0 + ((6 - 0) / 2)   // => Index 3 is the middle 

Next, the value stored at index location 3 is compared to the value we are searching for (let’s say that value is 100 in this example). So, we compare 9 (value at index 3) to 100, realizing it is not a match and that the target value (100) is greater than the middle value (9) the right half of the array is searched through in the next iteration:

[22, 77, 100]

The next step is again to find the middle value with the formula described above, with the lowIndex changed to the middle value’s index + 1. Alternatively, if the value being searched for were less than the middle value, the highIndex would be changed to middle value’s index -1. However, being that in our example the searched for value is greater than the middle value, the index of which is 3 (found in the first iteration of the formula described above), we add 1 to that and 4 is used as the new lowIndex —

newMiddle = 4 + ((6 - 4) / 2) // => 5 in the new middle index

The new middle index is 5, the value at which is compared to 100, being that this value is 77 it is determined to not be a match and also less than 100, so the next sub-array will be comprised of the values to the right of 77. This next sub-array in our example is made up of just 100 — and as the value we are searching for is 100, this comparison results in a match and now we know the value we are searching for is located at index 6.

JavaScript Example

function binarySearch(sortedArray, key) {     
     let start = 0;     
     let end = sortedArray.length - 1;
      
     while (start <= end) {      
          //find middle value of collection   
          let middle = Math.floor((start + end) / 2);   
       
          if (sortedArray[middle] === key) {  
 
                //if middle value is equal to value being searched    
                //for          
                return middle;   
      
          } else if (sortedArray[middle] < key) {  
               // if middle value is less than value of the sought 
               //after value, search collection to the right
               start = middle + 1;  
       
          } else {
                // otherwise, search collection to the left                        
                end = middle - 1;         
          }     
     }  
     // key wasn't found     
     return -1; 
}

Conclusion

The reason Binary Search is a preferable search algorithm is because it halves the searchable items with each iteration, decreasing the count of comparisons to be made each time. This is also why the run-time complexity is O(log n), as when the size of the input increases the run-time efficiency of the algorithm also increases.

Lines.. amiright?

An easy way to understand and remember the functionality of Binary Search is to think of how you would go about guessing a number within a range. Say you are really bored with your friend waiting for your table to open up at a busy restaurant, your friend asks you—

“Guess what number I am thinking of between 1 and 100.”

Now being an analytical genius, you decide to pick the middle number to see if your friend will give you a clue as to which half of the collection contains the number and thus greatly decreasing your options —

“Hmm…. is it 50?”

Your dinner companion says no and, being the generous friend you suspected, tells you that the number is less than 50. So it no longer makes sense for you to guess any number from 50 to 100— this portion of the collection is thrown out of consideration and you now know that the number lies somewhere between 1 and 49. Again, you decide to half the options by choosing the central number of this remaining collection —

“Is it 25?”

You are told no and that the number is greater than 25, so you eliminate any numbers between 1 and 25 from your consideration — leaving 26 through 49. The mid-way point between these two numbers is rounded to 38, so you guess this.

“No it is not 38, but the number is less than 38.”

You are now left with a range between 26 and 37, and guess the mid-way point value again until you either match the number your friend was thinking of (the chances of which increase with each halving of the collection) or until you only have one option left, which by default has to be the answer.

Although this is a very elementary explanation, I find visualization and association to be powerful tools in learning new concepts. Simplifying algorithms in this way can make them seem less intimidating to those covering these concepts for the first time and increase probability of recall.