Time Complexity of Binary Search

By Priyanshu Vaish|Updated : September 30th, 2022

The time complexity of binary search algorithm is a fast technique that works efficiently on a sorted list and large sorted array size. In binary search, it is important to make sure that the array should be sorted from which the element is to be searched, and if the array is unsorted, then it isn't easy to search the element.

The time complexity of binary search algorithm is an application of the divide and conquer approach. The time complexity of binary search algorithm takes less compilation time; therefore, the time complexity of binary search is better as it breaks the sorted array into two halves at every step of the algorithm.

Download Complete Algorithms Formula Notes PDF

What is Binary Search?

The binary tree is one of the divides and conquers algorithm applications, and the binary search applies to the sorted array. The binary search algorithm is efficient for finding the element in the sorted list of the element.

Suppose in binary search mj indicates the middle element of the sorted array. If the sought value is equal to the middle element of the sorted array, the position has been returned. Otherwise, do a binary search in the second half or the first half, if the key is more than the middle element.

Time Complexity of Binary Search Algorithm

The binary search algorithm can be implemented in both algorithms, that is, recursive or non-recursive algorithms. Suppose the binary search algorithm takes the sorted array and the key value found in the sorted array as an argument.

The time complexity of binary search algorithm given below is implemented using the non-recursive algorithm, which is as follows:

ALGORITHM BS (A[0...n-1], key)

p =0
q=n-1
while p ≤ q do
m = (p + q)/2 if key == = A[m]
return m
else
if key < A[m]
p = m - 1
return - 1
else
q = m + 1

Best Case Time Complexity of Binary Search

The best case time complexity of the binary search algorithm is when the target element appears in the middle of the list. The binary search algorithm always starts with the middle, whether the list is five or one million.

Therefore, the best case time complexity of binary search for a list of size N is O(1), independent of the input N size. In other words, the time complexity of binary search depends upon the best case as the key is matched with the mid element.

Worst Case Time Complexity of Binary Search

In the worst-case time complexity of binary search, the key is not found or the key is sometimes at the end of the sorted array. We consider the worst case to find the time complexity of binary search.

Let BS(n) denotes the number of times a key comparison is executed. Then the worst-case time complexity of binary search is denoted by BSworst(n). Since the algorithm divides the problem into two half after each comparison, therefore the recurrence relation is:

BSworst(n) = BSworst(n/2) + 1 for n > 1 C(1) = 1

On solving the above recurrence relation equation using the master theorem, to find the number of times, the search key is compared with the middle element in the sorted array as:
BSworst(n) = BSworst(n/2) + 1

a = 1; b=2
f(n) = n0 ; d = 0 case 2 holds:

Therefore,
BSworst(n)= Θ(ndlog n)
= Θ(n0 log n)
= Θ(log n)

Advantages of Time Complexity of Binary Search

Suppose the system has a large sorted array, and we need to find the element in that sorted array. In that case, the binary search algorithm is efficient as the time complexity of binary search is Θ(logn) which is minimum.

The binary search algorithm can be implemented non-recursively or recursively. We do not recursively implement the binary search algorithm because the algorithm implemented recursively requires many push pop operations.

Important GATE Topics

And Gate Truth TableMan Full Form
JK Flip FlopLan Full Form
JK Flip Flop Excitation TablePropped Cantilever Beam
Job Sequencing With DeadlinesTorsional Force
Knapsack Problem Using Greedy MethodPop Full Form

Comments

write a comment

FAQs on Time Complexity of Binary Search

  • The time Complexity of binary search in the worst case is that We need to reduce the search space till it has only a single element. Thus, the worst case in time complexity of binary search is O(logn).

  • In the best case, the time complexity of binary search is when the sought element is found in the first comparison. So we conclude that the time complexity of binary search is O(1) in best-case time.

  • The time complexity of binary search in worst and average case is logn because the recurrence relation of binary search is as follows:

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

    On solving the above relation, we get the answer as Θ(logn).

  • The disadvantage of binary search is that it takes the sorted array, and if the unsorted array is passed, it takes more time to find the element. Therefore the binary search is not a good choice for the unsorted array.

  • The iterative implementation of binary search is more efficient than recursive as the time complexity of binary search is the same in both cases. Still, there is a difference in the space complexity as the iterative implementation of binary search takes constant time O(1), whereas the recursive implementation of binary search takes O(logn).

Follow us for latest updates