Search Algorithm: Binary Search

Binary search is a search algorithm for finding an element in a sorted array by continuously chopping the search area into half. It’s an efficient algorithm because it uses only half of the space required by other, more complicated algorithms.

Binary search is also known as “divide and conquer” because it divides up work between two parts: finding the middle point (the pivot) and checking whether or not that point lies within your range of values.

Image representation of how binary search takes place

Binary search in daily life

Suppose we want to find the meaning of the word “Serenity”. One way to do this is to search for it in a dictionary, but this can take several minutes or hours.

To optimize this task, we will use a binary search. We go to the middle page and compare the words on that page with “Serenity”. If the word on the middle page is smaller than “Serenity”, then we can ignore all pages on the right side. If the word on the middle page is larger than “Serenity”, then we ignore all pages on the left side. We keep repeating this process until we find the word.

Binary search in coding practice

Imagine you are in a technical interview and you’re given a question where you have a sorted array for which you have to write a function that returns the index of the given element. The easiest way to solve this problem is to use a for a loop.

const arr= [“a”, “b”, “c”, “d”, “e”, “f”, “g”, “h”]
function binarySearch(arr, target){
    for(let i=0; i<arr.length; i++){
        if(arr[i] === target){
            return "Element found at index "+ i;
           }
    }
}

The above code works fine but you’ve failed the interview because your code needs to go faster.

A regular loop results in linear search or sequential search as it goes through each element of a list until the desired element is found, thus resulting in high time complexity.

Big O notation chart for linear search

Here’s how we can do better with the binary search:

1. First, we need to find the middle index of the given array
2. If the middle index is equal to the target we return that index
3. If that element is greater than the index the target must be somewhere on the left. So we find the middle of that slice of the array
4. If the element is less than the index of the target then we know that the target is somewhere on the right.
5. Repeat the process for that slice of the array

The result is a much faster algorithm with logarithmic time complexity because it is able to divide and conquer.

Big O notation chart for binary search

Binary Search Algorithm can be implemented in two ways which are:

1. Iterative Method
2. Recursive Method

That’s enough talking. Let’s write down code from both approaches.

Iterative method:

function binarySearch(target, arr) {
 let start = 0;
 let end = arr.length — 1;
 
 while (start <= end) {
     let mid = Math.floor((start + end) / 2);
         if (arr[mid] === target) {
              return “Element found at index “ + mid;
         } else if (arr[mid] < target) {
             start = mid + 1;
         } else {
             end = mid — 1;
         }
 }
 return “Element not found”;
}
const arr = [“a”, “b”, “c”, “d”, “e”, “f”, “g”, “h”]
binarySearch(“e”, arr)

Recursive method:

function binarySearch(arr, target, start, end) {
 if (start > end) {
     return “Not found”;
 }
 const middle = Math.floor((start + end) / 2);
 
 if (arr[middle] === target) {
     return “Target element found at index “ + middle;
 }
 if (arr[middle] > target) {
     return binarySearch(arr, target, start, middle — 1);
 }
 if (arr[middle] < target) {
     return binarySearch(arr, target, middle + 1, end);
 }
}
const arr = [“a”, “b”, “c”, “d”, “e”, “f”, “g”, “h”]
binarySearch(arr, “e”, 0, arr.length — 1)

Limitations of binary search:

The primary disadvantage of binary search is the requirement for the sorted array in order to carry out the binary search operation. According to the data structure, the output should come in a minimum number of steps, however, if the array is not sorted, the output is either incorrect or may come after a large number of steps.

We hope you enjoyed learning about binary search! Please feel free to reach out if you have any questions or comments.