Binary Search

by codecrucks · Published 20/09/2021 · Updated 03/08/2022

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²) + 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

After k iterations,

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

Binary tree created by binary search can have maximum height log₂n

So, k = log₂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₂n

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

Binary Search Example - Step 1 — Binary Search – Step 1

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

Binary Search Example - Step 2 — Binary Search – Step 2

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)⁰ = 1

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

= O(n⁰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₂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₂n)

Some Popular Problems Solved using Divide and Conquer

Additional Reading: Different Approaches