Understanding Binary Search Algorithm

Introduction

The problem of searching is very trivial. It goes like this:

There is an array of elements A[1..N] and we need to find the index of a given element in the array. In case the element is not present in the array, we can choose to return a specific value (say -1) which suggests that the element doesn’t exist in the array.

Binary Search is a very efficient and interesting searching algorithm. Regular searching algorithms take running time proportional to the size of the input. They are called linear time algorithm O(N) to be asymptotically true.

Binary Search on the other hand minimizes the running time for the search. It is a logarithmic time algorithm O(logN), where the base of the log is 2.

To provide this dramatic reduction in the running time, the input has to satisfy one condition and that is, the input array has to be sorted in increasing order.

You can modify the algorithm to work for arrays which are sorted in descending order as well.

How does the Binary Search Algorithm Works?

Ever tried looking for a word in the dictionary? Most of you will answer in Yes! And that is correct. If you know how to search in a dictionary, you know Binary Search 🙂

The Binary Search Algorithm works on one idea:

  • Eliminate as many elements as possible without looking at them.  (Best done by skipping half elements at a time)

For simplicity, let us consider an integer array which is sorted in ascending order

Let us try and find the integer K in the array. The binary search algorithm has the following steps:

  • Choose a range of elements say, [L .. R]
  • Find the middle of the range, say M
  • Look at the element at index M. Is K equal to the element at M – (Probing Step)
    • Yes – return M
    • No – Is the element at M greater than the K
      • Yes – shrink the range to left [L .. M-1]
      • No – shrink the range to right [M+1 .. R]
  • Repeat this until the range shrinks to just one element

For the below array, the arrows mark the probes we perform to find the number 2.

  • The biggest and darkest arrow divides the range at index 5 and eliminates a big chunk from the right.
  • The slightly smaller arrow divides the range at index 2 and eliminates the right part.
  • The third arrow divides the range at index 0 (truly speaking there is no elements in the left part)
  • The fourth arrow lands at the right element.

Binary Search

Source Code

The Binary Search code is really tough to get right. Most of the code I find fail for certain test cases. Here are few test cases which you must test when you write the code yourself

  1. Search for an element which is bigger than the last element in the range
  2. Search for an element which is smaller than the first element in the range
  3. Search for an element which is present in the middle of the range
  4. Search for an element which is at index 0
  5. Search for an element which is at index A.length – 1
  6. Search for an element which doesn’t exist in the array and is 1 greater than the element at the middle.

Conclusion

Binary Search is considered to be the easiest code, but it is not. Getting it right is complicated. Also, it is not just used for searching within a range of sorted elements but can be utilized for many other solutions too!

Here are few problems mentioned in Programming Pearls which can be solved using Binary Search!

  • Finding missing element in a sorted list
  • Finding missing element in a huge file of random numbers in a huge range.
  • Binary Search Trees are a good implementation of Binary Search
  • Solving Single Variable Equation

There are many more which we will discuss in the upcoming posts.

Stay connected and stay subscribed..