Binary Search Related

Binary-search-related questions are best solved by naming the variant before coding. Exact search asks whether mid equals target. Lower bound finds the first index whose value is at least target, while upper bound finds the first strictly greater value; both retain mid when it may be a boundary. Rotated arrays require identifying a sorted half, and binary search on answer requires a monotone feasibility predicate. In every case, write the invariant in one sentence, such as: the first feasible value remains between low and high. Use a midpoint formula that avoids overflow and updates that strictly shrink the interval. Duplicates can make rotation comparisons ambiguous, sometimes requiring decrementing high; discuss potential O(n) degradation. Test empty input, one element, all equal values, target absent, and answers at either endpoint. Standard array binary search is O(log n) time and O(1) space; the key is correctness of the invariant rather than memorizing a template.