Variations
Common variations of binary search include:
- Lower Bound. Returning the index of the smallest element larger than the needle (if the needle does not occur in the haystack). This is what the C++ standard library function lower_bound does.
- Upper Bound. Returning the largest element smaller than the needle (if the needle does not occur in the haystack). This is what the C++ standard library function upper_bound does.
- Bisection Search. When using a source code management system, such as git, use a variation of binary search to find the first commit that introduced (or fixed) a particular bug.
- Ternary Search. When searching through a unimodal distribution (i.e., an array where in the first part elements are sorted in increasing order and in the second part in decreasing order). Useful in practice when searching for, e.g., the vertex most distant from a given vertex in a polygon.
- Exponential Search. Useful for searching infinite ranges.
Caveats
- If the needle occurs multiple times in the haystack, the implementation above will only find some occurrence, not necessarily the first or the last;
- We are assuming that n is not too large. Otherwise, “n” would have to be an unsigned integer instead of a signed integer and we would also have to find another solution instead of return -1 for signalling that the needle does not occur in the haystack, since -1 is a signed value.
Enjoyed our tutorial on binary_search?
Cannot wait to understand more interesting algorithms and data structures? Subscribe to the TrulyUnderstandingAlgorithms Youtube channel to stay up to date with our videos.
Also consider liking our video and leaving a comment with topics that you would like to us cover in the future.