Practical Algorithms Tier 0: Binary Search
Binary search is a fundamental, yet powerful and frequently used algorithm. It has several interesting variations, which are usually skipped in a college CS class or “left as an exercise to the reader”.
It came to me during a coding contest that it is worth the time to possess the full power of binary search with all the beautiful variations, while being “practical” without formal math proves (and some horrible 1-indexed array in the math proves, or unnecessary abstraction to relate with binary-tree).
1. Basic Format
Given a sorted array of unique integers and a target integer, return the index if the target is found in the array, or -1 if not found.
This simple case is mostly useful to check if a target value is in a sorted array, for example the binary_search function in C++ Standard library.
For example, the result should be 2 in the test case below:
arr = [5, 6, 7, 9]
target = 7
2. Bisect_left
Given a sorted array of integers and a target integer, return the index of the first element equals to target, or the insert position of the target if no equal element exists.
This algorithm has two relaxed conditions comparing to the basic format:
- Allow duplicates in the array, instead of being unique
- Return the insert position if the target does not exists, instead of a sentinel value -1
For example, the result should be 2 in the test case below:
arr = [5,6,7,7,9]
target = 7
The trick of bisect_left is the loop invariant low . All elements on the left side of low are strictly less than target . So when the loop exits, element at low is the first element greater or equal to target . low is also the rank of target in the array.
This is the most commonly used binary_search algorithm.
3. bisect_right
Given a sorted array of integers and a target integer, return the index of the last insert position of target.
This algorithm essentially returns the index of the first element strictly larger than target. For example, the result should be 4 in the test case below:
arr = [5,6,7,7,9]
target = 7
The trick of bisect_right is the loop invariant high. Elements at and to the right of high are strictly larger than target .
For an iterative implementation of binary search, the time complexity is O(lgN) and space is O(1), where N is the length of the array.
For a recursion implementation, left as an exercise to the reader, the time complexity is O(lgN) but space is O(lgN) due to stack of function calls.
Q.E.D.
References:
https://en.wikipedia.org/wiki/Binary_search_algorithm https://docs.python.org/3/library/bisect.html http://www.cplusplus.com/reference/algorithm/binary_search/
