Binary Search Algorithm
The Binary Search Algorithm (BSA) is a method for finding an element in a sorted array. It uses the divide-and-conquer principle, repeatedly splitting the search space in half by comparing the target element with the middle element until the target is found or the search space is empty. It is also known as half-interval search.
Prerequisites for Binary Search
- For binary search to work correctly, the input data must be sorted.
- The data structure should support O(1) access to elements.
- The data structure should allow for comparison.
Typically, the array is sorted in ascending order. Binary search can also be applied to a descendingly sorted array, but in that case, the comparison logic must be reversed. If the sorting order is not handled properly, the algorithm may return incorrect results
Step-by-Step Algorithm
Key → Target element
Mid → Middle index of the search space
- Divide the search space into two halves by mid.
- Compare the mid element of the search space with the key.
- Repeat until the key is found or the search space becomes empty.
1. If the key == mid element, then the process is terminated.
2. If the key < mid element, then the left half is the next search space.
3. If the key > mid element, then the right half is the next search space.
How to Calculate the Middle Index
Not Recommended
If the left index or right index is a very large value (close to the maximum integer limit), then their sum (left index + right index) can overflow, leading to incorrect results or runtime errors. This issue is common in languages like C, C++, and Java, where integers have fixed-size limits.
Recommended
right index – left index is always a small and safe number. It prevents integer overflow produces the same correct middle index
Binary Search Algorithm
Binary Search Visualization
Binary Search Implementations
The binary search algorithm can be implemented by using the two methods given below:
- Iterative Binary Search Algorithm
- Recursive Binary Search Algorithm
Iterative Binary Search Algorithm: It involves a loop to keep dividing the search space in half until the target value is found or the search space is empty.
Recursive Binary Search Algorithm: It finds a target element in the searching space by splitting it into two halves and recursively calling itself until it finds the target element.
Time Complexity of Binary Search
The binary search algorithm divides the search space into two halves until the key element is found or the search space becomes empty. Due to this divide-and-conquer principle, binary search has a logarithmic time complexity. That’s why it is also called a logarithmic search
- Best Case: O(1) -> when the target is at the middle.
- Average Case: O(log n) -> The key element is randomly present in the search space
- Worst Case: O(log n) -> The key element is found only after the search space has been reduced to one element
Space Complexity of Binary Search
Space complexity differs slightly depending on the implementation.
- Iterative Approach: O(1) — uses constant extra space (fixed number of variables like left, right and mid).
- Recursive Approach: O(log n) — due to recursive call stack.
Drawbacks of Binary Search
Requires a Sorted Array
Binary search works only on sorted data. If the array is unsorted, it must be sorted first, which itself takes O(n log n) time—sometimes making binary search inefficient for one-time searches.
Not Suitable for Linked Lists
Binary search requires random access to elements (direct indexing). Since linked lists do not support random access, binary search is inefficient or impractical for such data structures.
Overhead for Small Datasets
For small arrays, the overhead of calculating midpoints and maintaining indices may make binary search slower than linear search, which is simpler and faster in such cases.
Data Must Remain Static
If elements are frequently inserted or deleted, maintaining the sorted order becomes costly. In such dynamic datasets, binary search may not be the best choice.
Recursive Implementation Uses Extra Space
The recursive version of binary search requires O(log n) extra space due to the recursion call stack, making it less space-efficient than the iterative approach.
References
- Wikipedia – Binary Search Algorithm
- GeeksForGeeks – Binary Search Explained
- Abdul Bari – Binary Search Algorithm