Binary Search Algorithm

Design and Analysis of Algorithms

8 min readJun 24, 2021

In computer science, binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search has been found to be more efficient than linear search when the array elements are in sorted order. An element that is to be searched from the array A[0 … n-1] is called as the KEY element.

Let A[m] be the mid element of array A. Then three conditions arise that needs to be tested while searching the array using this method:-

If KEY = A[m] then the desired element is present in the array (list).
Else if KEY <A[m] then search the left sub-list.
Else if KEY> A[m] then search the right sub-list.

This may be represented as:

For example, say the array elements are:
List = [ 23 36 | 45 51 | 55 57 61 70 82 ]
Value to search = 45

Pass-1: Mid = (1+9)/2 = 10/2 = 5
So, List [5] = 55 > 45
Hence, search value 45 in the left sub-list

Pass-2: Mid = (1+4)/2 = 5/2 = 2
So, List [2] = 36 < 45
Hence, search value 45 in the right sub-list

Pass-3: Mid = (3+4)/2 = 7/2 = 3
So, List [3] = 45 = 45
Hence, search value 45 is at 3rd position in the list.

Algorithm of Binary Search

Binary Search(list, n, value)

Note: Worst case time complexity (i.e. element not present) is O(log n) while the best case time complexity (element in middle) is O(1).

Function Binary search

Analysis: The basic operation in binary search is the comparison of search key i.e. KEY with array elements. To analyze efficiency of binary search we must count the number of times the search key gets compared with the array elements. The comparison is also called a three-way comparison because the algorithm makes the comparison to determine whether KEY is smaller, equal to or greater than A[m].

Explanation: In this algorithm, after one comparison the list of n elements is divided into n/2 sub-lists. The worst case efficiency is that the algorithm compares all of the array elements for searching the desired element. In this technique, one comparison is made and based on this comparison array is divided each time in n/2 sub-lists. Hence, the worst case time complexity is:

But as we consider the rounded down value when array gets divided, the above equations can be written as:

These two recurrence relations can be solved further. Assume n = 2^k , the equation- ( 1 ) becomes-

Using backward substitution method, we can substitute-

Then equation-3 becomes-

But as per equation- ( 2 )

Then we get equation- ( 4 )

But we have assumed earlier that-

Taking logarithm (base 2) on both sides we get-

Therefore,

That is why, the worst case time complexity of binary search is Θ(log2 n).
As Cworst (n) = log2 n + 1, we can verify equation-1 with this value.
Considering equation-2 we have-

Considering LHS-
Assume n = 2!
Substituting we get-

So, LHS = log2 i + 2

Now consider RHS-
Assume n = 2!
Substituting we get

As Cworst (n) = log2 n + 1
In the same manner,

So, RHS = log2 i + 2

Average Case Efficiency of Binary Search

If n=1
i.e., only element 11 is there, 1 → [11]; only 1 search is required to search some KEY

If n = 2 and search key = 22 then

Two comparisons are made to search 22.

If n = 4 and search key = 44 then

m = (0 + 3)/2 = 1
As A[1] = 22 and 22 < 44

Search right sub list, again
m= (2+3)/2 = 2

Again A[2] = 33 and 33 < 44, we divide the list. In the right sub list A[4] = 44 and key is 44.
Thus, total 3 comparisons are made to search 44.

If n = 8 and search key = 88 then

m = (0 + 7)/2 = 3
As A[3] = 44 and 44 < 88 search right sub list, again.

m = (4 + 7)/2 = 5
Again A[5] = 66 and 66 < 88, search right sub list again.

m = (6 + 7)/2 = 6
But A[6] = 77 and 77 <88.
Then search right sub list
m = (7 + 7)/2 = 7

A[m] = A[7] = 88. Is A[7] = 88 ?
Yes, the desired element is present.

Please note here that a total of 4 comparisons are made to search 88.
In summary,

From the Table 1, it is observed that-
log2 n + 1 = 0

For instance, if n = 2 then,
log2 2 = 1

Then,
c = 1 + 1 = 2

Similarly,
if n = 8 then
c = log2 n + 1
c = log2 8 + 1 = 3 + 1 = 4
So, c = 4

Hence, we can write that-
Average case time complexity of binary search is Θ(log2 n).

Advantages of Binary Search

It is an optimal searching algorithm using which we can search the desired elements efficiently.
It is faster than linear search.

Disadvantages of Binary Search

This algorithm requires the list to be sorted. Then only this method works better.

Applications of Binary Search

Database searching of records also uses this technique of binary search.
To solve non-linear equations with one unknown, this method may be used.

Differences b/w Binary Search and Linear Search

In nutshell, different time complexities of binary search are as listed in Table 2

Let us write its C program now. Both recursive and non-recursive approaches are shown below.

Recursive Binary Search Implementation

#include<stdio.h>
#include<conio.h>
#define SIZE 100
int n;
void main()
{
   int A[SIZE], KEY, i, flag, low, high;
   int BinSearch(int A[SIZE], int KEY, int low, int high);
   system("cls");      //clrscr() function can also be used here
   printf("\n\t Enter the size of your array:");
   scanf("%d", &n);
   printf("\n\t Enter the array elements:");
   for(i=0; i<n; i++)
       scanf("%d", &A[i]);
   printf("\n\t Enter the array element to be searched:");
   scanf("%d", &KEY);
   low = 0;
   high = n-1;
   flag = BinSearch(A, KEY, low, high);
   printf("\n\tThe element is at A[%d] location", flag);
   getch();
}
int BinSearch(int A[SIZE], int KEY, int low, int high)
{
    int m;
    m = (low + high) /2; //mid of the array is obtained
    if(KEY == A[m])
       return m;
    else if(KEY <A[m])
        BinSearch(A, KEY, low, m-1); //search left sub-list
    else
        BinSearch(A, KEY, m+1, high); //search right sub-list
}

OUTPUT (after running)
Enter the size of your array: 5
Enter the array elements: 10 20 30 40 50
Enter the array element to search: 20
The element is at A[1] location.

Non-recursive Binary Search Implementation

#include<stdio.h>
#include<conio.h>
#define size 100
int n;
void main()
{
    int A[size], key, i, flag, low, high;
    int BinSearch(int A[size], int key);
    system("cls");    //clrscr() function can also be used here
    printf("\n\t Enter the size of your array:");
    scanf("%d", &n);
    printf("\n\t Enter the array elements:");
    for(i=0; i<n; i++)
        scanf("%d", &A[i]);
    printf("\n\t Enter the array element to be searched:");
    scanf("%d", &key);
    flag = BinSearch(A, key);
    if(flag == -1)
        printf("\n\t The element is not present");
    else
    printf("\n\t The element is at A[%d] location", flag);
    getch();
}
int BinSearch(int A[size], int key)
{
    int m, low, high;
    low = 0;
    high = n-1;
    while (low <= high)
   {
    m = (low + high) /2; //mid of the array is obtained
    if(key == A[m])
         return m;
    else if(key <A[m])
         high = m-1; //search left sub-list
    else
         low = m+1; //search right sub-list
   }
  return -1;   // if element is not present in the list
}

Output-1 (after running)
Enter the size of your array: 6
Enter the array elements: 10 20 30 40 50 60
Enter the array element to search: 50
The element is at A[4] location.
Output-2 (after running)
Enter the size of your array: 5
Enter the array elements: 10 20 30 40 50
Enter the array element to search: 80
The element is not present.