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)
while p ≤ q do
m = (p + q)/2 if key == = A[m]
if key < A[m]
p = m - 1
return - 1
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:
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 Table||Man Full Form|
|JK Flip Flop||Lan Full Form|
|JK Flip Flop Excitation Table||Propped Cantilever Beam|
|Job Sequencing With Deadlines||Torsional Force|
|Knapsack Problem Using Greedy Method||Pop Full Form|