# 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.

## 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.

POPULAR EXAMS
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com