arrayssearchingtips
Give each binary search boundary a meaning
Anonymous
For a monotone predicate, search for the first true position. Keep lo as known-false and hi as known-true, using sentinels just outside the range when needed. While hi - lo > 1, test the midpoint and move the matching boundary. Return hi; if every value is false, it remains the end sentinel. This takes O(log n) predicate checks.
0