Binary Search Algorithm
Binary Search is the most well-known search technique in the programming world. The significant advantage of Binary search is that it is faster than the linear search method. So, let’s talk about its algorithm.
Algorithm:
The first important thing in Binary search is the array on which binary search is implemented must be a sorted array. Binary Search will not work on the unsorted array.
In binary, we first compare the mid element of the array with the element which has to be found. If the mid element and the target element are the same then just return the mid index. If they are not the same then check if the target value is greater or less than the mid element.
If the target element is less than the mid element we move towards the left portion of the array or if it is greater than the mid element then we move towards the right portion of the array. Because the list is sorted so the target element cannot be on the other sides of the array depending upon the comparison with the mid element.
After it, we compare it with the mid element of that portion and do the same procedure until the element is found, or if we shrink to the size of one element only and in this case, we just return the -1 which means the target element is not found.
Analysis:
As I said earlier Binary search is faster than linear search because it is just chopping down the array and narrowing the search portion.
So in the best case, the Time Complexity of Binary Search is O(1) and in the worst case, its Time Complexity is O(log n) which is much smaller than the linear Search time complexity O(n).
Code :
Here is the code for recursive and iterative Binary Search in C++.
