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.

**S[ ]** – The sorted array with data.

**n** – It is the number of elements in the array.

**key **– 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 **key **is **65**, then **mid **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 **low = 5** and** high = 9.**

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 **low = 5** and **high = 6.**

We only have two element to search for the key. The **mid **is calculated using** high = 6** and **low = 5**.

```
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, **mid **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.

```
N <= 2^L - 1
N + 1 <= 2^L
Where
N is total number of nodes in the decision tree
L is the number of levels in the decision tree
```

The decision tree above is from an array of size 7 where root = 3 is the mid value. If we compute other mid values we get the above decision tree. The difference between parent and child is 2^x where x = 0, 1, 2 ,….

**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 (n) of an array for binary search can be different.

Therefore,

```
N + 1 >= n + 1
where
N + 1 is the number of nodes in the tree
n + 1 is the number of elements in the array
```

Using the above information we can say that

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

Taking log of equation will give us, log (n + 1). 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.