Binary Search (and its Variants)

Binary search turns a slow linear scan into a handful of comparisons by repeatedly halving a sorted range. It is the engine behind database indexes, autocomplete, and 'search the answer' optimization. In this challenge you implement the classic search, then the lower_bound and upper_bound variants that power range and count queries, then binary search on a rotated array, and finally the search-the-answer pattern that finds the smallest value satisfying a monotonic predicate.