Questions to ask before binary searching

The first question is is there a monotonic predicate over the search space? Sortedness is the common special case, but the real requirement is that some yes/no test flips exactly once as you move across the space — false…false true…true. A rotated sorted array is not sorted, yet "is a[mid] in the same sorted half as the target" is checkable, so binary search still works. Without monotonicity, discarding half the space is not justified.

Second, do I have `O(1)` random access? Binary search on a linked list gives no benefit, because reaching the middle is O(n). Third, am I looking for a value or a boundary? Finding an exact value uses lo <= hi and returns on equality; finding the first index where the predicate is true uses lo < hi with hi = mid and never returns early. Mixing the two templates is the source of most infinite loops and off-by-ones.

Fourth, is the search space the input or the answer? In Binary Search on the answer, the space is a range of candidate answers (minimum speed, minimum capacity, maximum distance), and the predicate is a feasibility check that costs O(n). The signal is "minimize the maximum" or "maximize the minimum" phrasing with a feasibility check that is monotonic in the candidate. The candidate should be able to prove monotonicity ("if speed s works, so does s + 1") before searching.