Time Complexity of Binary Search
By BYJU'S Exam Prep
Updated on: September 25th, 2023
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.
Table of content
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.
