Binary Search Algorithm

The binary search algorithm is very popular search algorithm. It is also known as half-interval search or uniform binary search as it split the array of data into two equal parts recursively until a solution is found. The array in binary search must be sorted.

Binary search employ an algorithm design technique known as divide and conquer. In this technique, a given problem is divided into smaller sub-problems and this is done until no more sub-division is possible.

Then solution to the smallest problem is found and all solutions are combined to get the overall solution to the problem. The divide and conquer technique is not limited to binary search; therefore, we shall discuss this separately in another article.

Binary Search Algorithm

Algorithm Binary Search (S, n , key)
{
   low := 0
   high = n - 1
   while (low <= high)
   {
      //compute the mid value
      mid = low + (high - low)/2
      if (key < S[mid]) then
          high := mid - 1
      else if ( key > S[mid]) then
          low := mid + 1
      else
          return mid
   }
}

The elements of binary search are as follows.

– The sorted array with data.

– It is the number of elements in the array.

– The search key to be found.

Mid Value

The mid value is most important in binary search as it split the array in to two parts. Then the sub-array is split in the similar way based on divide and conquer technique. The mid is an index of the element in the middle of the array.

mid = low + (high - low)/2

How Binary Search Works?

The binary search works on a sorted array. Suppose we have an array with elements in non-decreasing order. To search for a given key, binary search will compute the mid value and thus break the array into equal halves. The key is compared with array element with index value as mid.

Suppose our is , then is calculated as follows.

mid = 0 + ( 9 - 0 ) / 2 = 0 + 4 = 4

//S[4] = 48
//key > S[mid] ( 65 > 48  )
//low = mid + 1

low = 4 + 1 = 5

//low = 5 and high = 9 

Now we will consider the upper half of the array for searching with and .

We now have to compute a new mid value in the upper half of the array to search for the key.

mid = 5 + ( 9 - 5 )/2 
mid = 5 + 4/2 
mid = 5 + 2 
mid = 7

//S[7] = 75
//key < S[mid] (65 < 75 )
//high = mid - 1

high = 7 - 1 
high = 6

//now, low = 5 and high = 6

We will compute the new mid value with and .

We only have two element to search for the key. The is calculated using and .

mid = 5 + ( 6 - 5 )/2
mid = 5 + 0
mid = 5 

//S[5] = 54
//key > S[mid] ( 65 > 54 )
//low = mid + 1

low = 5 + 1
low = 6

//low = 6 and high = 6 

The high and low are equal which will be last iteration of while loop in the binary search algorithm. However, is still calculated for the last iteration.

mid = 6 + ( 6 - 6 )/2
mid = 6 + 0
mid = 6

//key == S[mid] ( 65 == 65 ) 
//mid is returned 

Time Complexity Of Binary Search

How much time binary search take on average to search for an element in the array ? Before we try to answer that question, let us understand the decision tree for binary search.

A decision tree is the pattern that the binary search follows to get to the element. Suppose that each of the node in binary search has two child including the root. Then the total number of nodes in the decision tree is given by the equation.

\begin{aligned}
&N <= 2^L - 1\\
&N + 1 <= 2^L\\

&Where \\
&N \hspace{1mm} is \hspace{1mm}total \hspace{1mm} number \hspace{1mm} of \hspace{1mm} nodes\hspace{1mm}  in \hspace{1mm} the\hspace{1mm}  decision\hspace{1mm} tree.\\
&L \hspace{1mm} is \hspace{1mm} the \hspace{1mm} number\hspace{1mm} of \hspace{1mm}levels\hspace{1mm}  in \hspace{1mm} the\hspace{1mm} decision\hspace{1mm} tree.
\end{aligned}

The decision tree above is from an array of size where is the mid value. If we compute other mid values we get the above decision tree. The difference between parent and child is where .

Relationship between Nodes and Elements of Sorted Array

In the above decision tree, we have number of elements that match with the tree. Each of the node in the decision tree has exactly 2 child. But this is not possible all the time because number of elements of an array for binary search can be different.

Therefore,

\begin{aligned}
&N + 1 >= n + 1\\
&where \\
&N + 1  \hspace{1mm}is \hspace{1mm}the\hspace{1mm} number\hspace{1mm} of\hspace{1mm} nodes\hspace{1mm} in the\hspace{1mm} tree\\
&n + 1\hspace{1mm} is \hspace{1mm}the \hspace{1mm}number \hspace{1mm}of \hspace{1mm}elements\hspace{1mm} in \hspace{1mm}the \hspace{1mm}array
\end{aligned}

Using the above information we can say that

2^L >= N + 1 >= n + 1

Taking log of equation will give us, . Therefore, the time complexity of binary search in average and worst case is given as .

C++ Implementation of Binary Search

#include <iostream.h>
#include <stdio.h>
#include <conio.h>
int main()
{
   int S[10] = { 6, 23, 34, 42, 48, 54, 65, 75, 81, 95};
   int key,low,high;
   int mid= 0;
   //Read key value
   cout <<"Enter your key:" ;
   cin >> key;
   low = 0;
   high = 9;
   //Binary search
   while(low <= high)
   {

      mid = low + (high - low)/2;

      if (key < S[mid])
      {
	high = mid - 1;
      }
      else if ( key > S[mid])
      {
	  low = mid + 1;
      }
      else
      {

      cout <<"Key found at " << mid << ": " << S[mid]<<endl;
      return mid;
      }
   }
 }

Input:

Enter your key: 65

Output:

Key found at 6:  65

In the next article, we will discuss another variant of binary search called the interpolation search.