Binary Search Time Complexity | Introduction | Algorithm

What is Binary Search?

The binary search algorithm is one of the most efficient algorithms in terms of speed or time complexity. The main problem in this search algorithm is that the data must be sorted in increasing order or alphabetically and it must be started from the middle index of the data array. It is one of the most strong search algorithms for a sorted list. Suppose, you want to find a name from the phone list. The binary search is best for this problem. Because the phone list is always sorted in alphabetical order.

Fig. 01: Drawback of binary search

Time Complexity of Binary Search

The time complexity of this algorithm is also lower than the others. We have to discuss the algorithm of this search technique before measuring the time complexity of the binary search. So, What is said in this algorithm?

Algorithm for Binary Search

Step 1: Initialize all the required parameters. BEG = LOWER BOUND, END = UPPER BOUND & MID = INT ((BEG+END)/2).

Step 2: Repeat step 3 and step 4 while BEG<=MID and DATA[MID]!=ITEM is fulfilled.

Step 3: Condition inside the while loop.

If ITEM < DATA [MID], then do

Set END = MID - 1

Else do,

Set MID = MID + 1

End of the if and else loop

Step 4: Again set MID = INT ((BEG+END)/2)

End of the step 2 while loop.

Step 5: If data is found in search, then set the index

If DATA[MID] = ITEM, then do

Set LOCATION = MID

Else do,

Set LOCATION = NULL

End of the if and else loop

Step 6: End of the algorithm

We can see that the algorithm's time complexity compares to Big O (n) time complexity is the same. Here, n is the length of the input data array. As we know, the search algorithm mostly depends on the comparison of the items. In this algorithm, the comparison is less than other search or sorting algorithms because it starts from the middle of the data array. That is how the binary search algorithm reduces the number of comparisons. As the algorithm starts in the middle, it needs to process half-size of the input array data. So, the needed comparison will be,

Comparison number = 2ⁿ where n is the length of the data array

For the time complexity representation, the 2ⁿ can be written as log₂n. So the time complexity of the binary search algorithm is,

Time Complexity = Number of comparison

= 2ⁿ

= log₂n

= O (log₂ n)

The worst-case happened when the searching number in the last index of the array and time complexity is O ( log₂ n). The best-case occurs when the searching number in the first index of the input data array and its time complexity will be O (1).

Fig. 02: Time complexity of binary search

Overall, the time complexity of the binary search algorithm is O ( log₂ n).

The above-mentioned algorithm implementation is given below in the C++ language. Hope this will help.

Binary Search in C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, i, s;
    cout<<"How many number: ";
    cin>>n;
    int a[n];
    cout<<"Numbers are: ";
    for (i=0; i<n; i++)
    {
        cin>>a[i];
    }
    cout<<"Enter a number for search :";
    cin>>s;
    int high, low, mid, ind;
    high=n-1;
    low=0;
    ind=-1;
    mid=-1;
    while( high>= low)
    {
        mid = low+(high-low)/2;
        if(a[mid]==s)
        {
            ind = mid;
            break;
        }
        if(a[mid]<s)
        {
            low= mid+1;
        }
        else
        {
            high=mid-1;
        }
    }
    if(ind==-1)
    {
        cout<<s<<" not found"<<endl;
    }
    else
    {
        cout<<s<<" found at index "<<ind<<endl;
    }
    return 0;
}