# 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.

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 :

1. 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].
2. 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]
3. 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 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.

### 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/22) + 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/23)  + 3

.

.

After k iterations,

T(n)   =   T(nk) + k

Binary tree created by binary search can have maximum height log2n

So, k = log2n ⇒ n = 2k

T(n) = T(2k/2k)  + k

= T(1) + k

From base case of recurrence,

T(n) = 1 + k = 1 + log2n

T(n) = O(log2n)

### 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 log2 n comparisons, which will turn out as T (n) =  O(log2 n).

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

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/

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 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.

bd = (3/2)0 = 1

Here, a = bd, so from master method T(n) = O(ndlog n)

= O(n0log n)

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