Binary Search
Binary search is a search method used to locate the position of a target value in a sorted array. It divides the search range in half until finding the target value or depleting the range. This is done by comparing the target with the middle value of the search space.
Requirements for Using Binary Search Algorithm in a Data Structure:
To use Binary Search algorithm:
The data structure must be sorted.
Accessing any element in the data structure should take constant time.
Binary Search Algorithm:
In this algorithm,
- Divide the search space into two halves by finding the middle index “mid”.
Finding the middle index “mid” in Binary Search Algorithm
Compare the middle element of the search space with the key.
If the key is found at middle element, the process is terminated.
If the key is not found at middle element, choose which half will be used as the next search space.
If the key is smaller than the middle element, then the left side is used for next search.
If the key is larger than the middle element, then the right side is used for next search.
This process is continued until the key is found or the total search space is exhausted.
How does Binary Search Algorithm work?
To understand the working of binary search, consider the following illustration:
Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}*, and the **target = 23**.*
First Step: Calculate the mid and compare the mid element with the key. If the key is less than mid element, move to left and if it is greater than the mid then move search space to the right.
- Key (i.e., 23) is greater than current mid element (i.e., 16). The search space moves to the right.
Binary Search Algorithm : Compare key with 16
- Key is less than the current mid 56. The search space moves to the left.
Binary Search Algorithm : Compare key with 56
Second Step: If the key matches the value of the mid element, the element is found and stop search.
Binary Search Algorithm : Key matches with mid
How to Implement Binary Search Algorithm?
The Binary Search Algorithm can be implemented in the following two ways
Iterative Binary Search Algorithm
Recursive Binary Search Algorithm
Complexity Analysis of Binary Search Algorithm:
Time Complexity:
Best Case: O(1)
Average Case: O(log N)
Worst Case: O(log N)
Auxiliary Space: O(1), If the recursive call stack is considered then the auxiliary space will be O(logN).
Applications of Binary Search Algorithm:
Binary search can be used in machine learning for algorithms like neural network training or finding optimal hyperparameters.
It can help in computer graphics for tasks like ray tracing or texture mapping.
Binary search is handy for searching databases.
Advantages of Binary Search:
Faster than linear search, especially for big arrays.
More efficient than other similar searching algorithms like interpolation search or exponential search.
Suitable for searching large datasets stored in external memory, like on a hard drive or in the cloud.
Disadvantages of Binary Search:
The array must be sorted.
Requires the data structure to be stored in contiguous memory locations.
Elements in the array must be comparable for binary search to work.
Important Differences
| Linear Search | Binary Search | | --- | --- | | In linear search input data need not to be in sorted. | In binary search input data need to be in sorted order. | | It is also called sequential search. | It is also called half-interval search. | | The time complexity of linear search O(n). | The time complexity of binary search O(log n). | | Multidimensional array can be used. | Only single dimensional array is used. | | Linear search performs equality comparisons | Binary search performs ordering comparisons | | It is less complex. | It is more complex. | | It is very slow process. | It is very fast process. |