Binary Search Fundamentals

Opening scenario

Search in Rotated Sorted Array (LC 33). A sorted array was rotated at an unknown pivot ([4,5,6,7,0,1,2]). Find target's index in O(log n), or -1. Then the follow-up: Find K Closest Elements (LC 658) — given a sorted array, a target x, and a count k, return the k values nearest to x, in sorted order.

LC 33 assumes distinct array values, so the sorted side can be identified unambiguously. LC 658 requires 1 <= k <= len(arr) and breaks equal-distance ties in favor of the smaller value. Start by identifying which candidate positions a midpoint comparison can safely eliminate. LC numbers identify LeetCode problems.

Question progression

Q1 — What property makes halving the search space correct?

Question: Linear scan finds target in O(n). Binary search claims O(log n). What must be true about the array for halving to be valid, and where does it break?