# Binary Search

The binary search method is more efficient than the linear search method. The array must be sorted for binary search, which is not necessary for linear search. Binary search Binary search is a search strategy based on divide and conquer. The method divides the list into two halves at each step and checks weather the element to be searched is on the top or lower side of the array. If the element is located in the center, the algorithm returns.

**Suggested Reading: **Linear Search

Let us assign minimum and maximum index of the array to variables *low* and *high*, respectively. The middle index is computed as (low + high)/2.

In every iteration, the algorithm compares the middle element of the array with a key to be searched. Initial range of search is A[0] to A[n – 1]. When the key is compared with A [*mid*], there are three possibilities :

- The array is already sorted, so if key < A[mid] then key cannot be present in the bottom half of the array. Search space of problem will be reduced by setting the
*high*index to (mid – 1). New search range would be A[*low*] to A[*mid*– 1]. - If key > A[
*mid*] then the key cannot be present in the upper half of the array. Search space of problem will be reduced by moving the*low*index to (mid + 1). New search range would be A[*mid*+ 1] to A[*high*] - If key = A[
*mid*], the search is successful and algorithm halts.

This process is repeated till index *low* is less than *high* or element is found.

## Algorithm for Binary Search

**Algorithm **BINARY_SEARCH(A, Key)
// Description : Perform a binary search on array A
// Input : Sorted array A of size n and Key to be searched
// Output : Success / Failure
low ← 1
high ← n
**while **low < high **do**
mid ← (low + high) / 2
**if **A[mid] == key **then**
return mid
**else if **A[mid] < key **then**
low ← mid + 1
** else**
high ← mid – 1
** end
end
return **0

Binary search reduces search space by half in every iteration. In a linear search, the search space was reduced by one only.

If there are n elements in an array, binary search, and linear search have to search among (n / 2) and (n – 1) elements respectively in the second iteration. In the third iteration, the binary search has to scan only (n / 4) elements, whereas linear search has to scan (n – 2) elements. This shows that a binary search would hit the bottom very quickly.

## Complexity Analysis of Binary Search

### Best Case:

In binary search, the key is initially compared to the array’s middle element. If the key is in the center of the array, the algorithm only does one comparison, regardless of the size of the array. As a result, the algorithm’s best-case running time is T(n) = 1.

### Worst Case:

Every iteration, the binary search search space is decreased by half, allowing for maximum log2n array divisions. If the key is at the leaf of the tree or it is not present at all, then the algorithm does log2n comparisons, which is maximum. The number of comparisons increases in logarithmic proportion to the amount of the input. As a result, the algorithm’s worst-case running time would be T(n) = O(log2 n).

The problem size is reduced by a factor of two after each iteration, and the method does one comparison. Recurrence of binary search can be written as T(n) = T(n/2) + 1. Solution to this recurrence leads to same running time, i.e. O(log2n). Detail derivation is discussed here:

In every iteration, the binary search does one comparison and creates a new problem of size n/2. So recurrence equation of binary search is given as,

T(n) = T(n/2) + 1, if n > 1

T(n) = 1, if n = 1

Only one comparison is needed when there is only one element in the array. That’s the trivial case. This is the boundary condition for recurrence. Let us solve this by iterative approach,

T (n) = T(n/2) + 1 **…(1)**

Substitute n by n/2 in Equation (1) to find T(n/2)

T(n/2) = T(n/4) + 1 **…(2)**

Substitute value of T(n/2) in Equation (1),

T(n) = T(n/2^{2}) + 1 **…(3)**

Substitute n by n/2 in Equation (2) to find T(n/4),

T(n/4) = T(n/8) + 1

Substitute value of T(n/4) in Equation (3),

T(n) = T(n/2^{3}) + 3

.

.

After k iterations,

T(n) = T(n^{k}) + k

Binary tree created by binary search can have maximum height log_{2}n

So, k = log_{2}n ⇒ n = 2^{k}

T(n) = T(2^{k}/2^{k}) + k

= T(1) + k

From base case of recurrence,

T(n) = 1 + k = 1 + log_{2}n

T(n) = O(log_{2}n)

### Average Case:

The average case for binary search occurs when the key element is neither in the middle nor at the leaf level of the search tree. On average, it does half of the log_{2 }n comparisons, which will turn out as T (n) = O(log_{2} n).

The complexity of linear search and binary search for all three cases is compared in the following table.

Best case | Average case | Worst case | |

Binary Search | O(1) | O(log_{2}n) | O(log_{2}n) |

Linear Search | O(1) | O(n) | O(n) |

## Example of Binary Search

**Example: Find element 33 from array A {11, 22, 33, 44, 55, 66, 77, 88} using binary search.**

**Solution:**

The array is already sorted, so we can directly apply binary search on A. Here Key = 33.

**Iteration 1: **Initial search space

low = 1, high = 8,

mid = low + high) / 2 = (1 + 8)/ 2 = 9/2 = 4

A[mid] = A[4] = 44

As Key < A[4], update high

high = mid – 1 = 4 – 1 = 3

**Iteration 2 : **New search space

low = 1, high = 3,

mid = (low + high) / 2 = (1 + 3)/ 2= 4/2 = 2

A[mid] = A[2] = 22

As Key > A[2], update low

low = mid + 1= 2 + 1 = 3

**Iteration 3 : **New search space

low = 3, high = 3,

mid = (low + high) / 2 = (3 + 3)/ 2= 6/2 = 3

A[mid] = A[3] = 33

Key = A[3], An element found, so return mid

## Simulation

Simulation of binary search and linear search is illustrated in following figure:

Image Source: https://www.interviewbit.com/courses/programming/topics/binary-search/

## Ternary Search

A binary search splits an array into two parts. If it splits an array into three parts, write down recurrence relation and complexity

Ternary search divides the array into three parts, so instead of mid-index, we would compute *oneThird *and *twoThird* indices of the array as shown in the figure. The array is divided in three parts: *upper*, *middle *and *lower*.

low = 0

high = 8

oneThird = (low + high) / 3 = (0+8) / 3 = 2

two Third = 2/3 * (high – low) / 3 = 2/3*(8) / 3 = 5

Initially, *low* and *high* indices are pointing to a minimum and maximum index of an array.

If the key is less than the A[oneThird], then it will be definitely in the upper part of the array, so *high* index is updated to oneThird – 1.

If the key is greater than A[twoThird], then it will be definitely in the lower part of the array, so *low* index is updated to twoThird + 1

And if the key is between A[oneThird] and A[twoThird] then *low* and *high* indices will be updated to (oneThird + 1) and (twoThird – 1) respectively.

### Algorithm for Ternary Search:

**Algorithm **TERNARY_SEARCH(A, Key)
// Description : Perform a ternary search on array A
// Input : Sorted array A of size n and Key to be searched
// Output : Success / Failure
low ← 1
high ← n
**while **low ← high **do**
oneThird ← floor(high – low) / 3
twoThird ← floor(2/3 * (high - low))
**if** A[oneThird] == key **then**
**return **oneThird
** else if **A[twoThird] == key **then**
**return **twoThird
**else if **key < A[oneThird] **then**
high ← oneThird - 1
**else if **key > A[oneThird] **and** key < A[twoThird] **then**
low ← oneThird + 1
high ← twoThird - 1
**else**
low ← twoThird + 1
**end
end
return **0

There are two cases of ternary search :

**Case 1**** :**** **Two comparisons fix the position in one of the parts of the array, and the size of the new problem would be n/3. Recurrence for this case would be T(n) = T(n/3) + 2

**Case 2**** :**** **After single comparison list is divided into two parts of size 1/3 and 2/3 respectively. In the worst case, the key will be in the larger part of size 2/3. Recurrence for this case would be

T(n) = T(2n/3) + 1.

Solving the recurrence T(n) = T(2n/3) + 1.

The recurrence T(n) = T(2n/3) + 1 is of the form

T(n) = aT(n/b) + f(n), with a = 1, b = 3/2 and f(n) = 1 with degree of polynomial d = 0.

b^{d} = (3/2)^{0} = 1

Here, a = b^{d}, so from master method T(n) = O(n^{d}log n)

= O(n^{0}log n)

= O(log n) Thus, worst case running time of ternary search is O(logn).

## Linear Search vs. Binary Search

Linear Search | Binary Search |

Simple but not efficient. | Efficient but not as simple as a linear search. |

Works on the random list also | The list must be sorted. |

In the worst case, all elements are compared with the key. | In the worst case, only log_{2}n elements are compared with the key. |

In the best case, the element is in the first position of the array. | In the best case, the element is in the middle of the array. |

Average case = Worst case = O(n) | Average case = Worst case = O(log_{2}n) |

## Some Popular Problems Solved using Divide and Conquer

- Linear Search
- Binary Search
- Convex Hull
- Max-Min Problem
- Larger Integer Multiplication
- Strassen’s Matrix Multiplication
- Finding Exponent Problem
- Merge Sort
- Quick Sort

Additional Reading: Different Approaches