A blog on Binary Search Algorithm
What is Binary Search Algorithm?
Binary Search is a very significant algorithm for programmers and coders to know since it gives a productive and efficient method for tracking down items in an arranged or sorted list, and it exhibits concepts that act as a base concept for numerous other algorithms.
Binary Search is one of the quickest search algorithms since it halves the pursuit space with every iteration. Binary search requires an arranged set that likewise has constant access times. This truly intends that, of the multitude of data structures, just sorted arrays are reasonable and suitable for Binary Search.
Like all Divide and Conquer algorithms, Binary Search initially partitions an enormous array into two smaller subarrays and afterward recursively (or iteratively) works the subarrays. Be that as it may, rather than dealing with both subarrays, it disposes of one subarray and progresses forward with the second subarray. This choice of disposing of one subarray is made in only one comparison.
How it works:
This is how the search and division of sub-arrays are done in binary search:
Step 1:
Observe the center component in the current search space. On the off chance that this middle component is the targeted component, return its index and stop the process.
Step 2:
Else, decide if the objective component is to the left or right of the middle component, and lessen the search space to that half containing the component.
Step 3:
Repeat the interaction on the divided inquiry space: distinguish the center component, return its index, assuming it’s the objective component, or figure out which half of the search space the component will be in, and decrease the process space to that half.
Step 4:
This search will go on until the objective component is found or the same length as there are components in the search space. On the off chance that the pursuit space contains no elements, the algorithm has failed to track down the objective component in the array, and returns -1
The Pseudo-code:
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound — lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint — 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure
Time and Space Complexity:
The worst case of Binary Search occurs when the element is to search is at the first index or last index.
In this case, the total number of comparisons required is logN comparisons.
Therefore, the Worst Case Time Complexity of Binary Search is O(logN).
The space complexity in the recursive implementation of Binary Search is O(logN, whereas in an iterative implementation of Binary Search, the space complexity will be O(1).
As compared to other Algorithms:
A Binary Search Tree (BST) offers better insertion and deletion times, yet BSTs can become degenerate (when each parent node has only one child node), which decreases searching time to linear. Balanced trees are an answer for keeping search time to log_2n, however finding ranges in a balanced tree is harder, and finding the smallest or largest element is no longer constant time.
As far as speed, just hash maps are quicker than binary search, since hash guides can decide if a component is in a set in constant time. Nonetheless, hashing can’t tell us the succeeding smallest or biggest thing with respect to the original item we looked for. Hashing additionally can’t give us every one of the things in a given reach, or the smallest or greatest item in the array.
A downside of Binary Search is that it requires an arranged array, in light of the fact that arranged arrays have linear insert and erase time complexities. The option is unsorted arrays with consistent insertion and deletions, yet with linear inquiry time. Despite the fact that linear searching has a magnificent territory of reference for the CPU cache, this region isn’t to the point of outperforming Binary Search.
