Classic and Rotated

What is this?

This is binary search in its most recognizable form: you have a sorted list, and you want to find a value (or the spot where it would go) by halving the range each step. The twist is "rotated" arrays — a sorted list that someone cut and swapped, like a deck of cards split in the middle, so it reads 4 5 6 7 0 1 2. Even though the whole thing isn't sorted anymore, at every midpoint one of the two halves still is, and that's enough of a clue to keep throwing half the array away.

💡 Fun fact: The "spin a sorted array" trick behind rotated search isn't just an interview gimmick — it's how circular buffers and log-rotation systems store data that wraps around the end and continues at the start, so the newest entry can sit anywhere in the array.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Binary search works whenever you can ask a yes/no question of the middle element and throw away the half that cannot contain the answer. Once you can decide "which side is the target on?" in O(1), the search collapses from O(n) to O(log n) — even when the array is rotated or the structure is subtler than "is this the value?".

The pattern

Every problem here keeps two pointers, lo and hi, and repeatedly inspects mid. The art is choosing the predicate that decides which half survives, and being disciplined about whether you want the first match, the last match, or simply any match.

Three reflexes carry the whole chapter. First, when duplicates or boundaries matter, run binary search twice — once biased left, once biased right — to pin down a range instead of a point. Second, when the array is rotated, at every step one half is guaranteed sorted; compare mid against an endpoint to find that sorted half, then check whether the target lies inside it. Third, when there is no obvious "value to match," search on a derived property — a parity rule, or a comparison of mid to its neighbour — that still cleanly splits the array.

The invariant is what keeps you safe: name what lo and hi mean before the loop, and make sure every branch preserves it.

The problems

Find First and Last Position of Element in Sorted Array — locate the leftmost and rightmost occurrence of a target. Run two boundary searches: one that keeps moving left on a match, one that keeps moving right. Two O(log n) passes give the full range.

Search in Rotated Sorted Array — a sorted array rotated at an unknown pivot. At each mid, one half is sorted; figure out which, decide whether the target falls inside that sorted half, and discard the other.

Find Minimum in Rotated Sorted Array — the minimum is the single point where order breaks. Compare mid to the right endpoint: if mid > right, the dip is to the right; otherwise it is at mid or to its left.

Single Element in a Sorted Array — every element appears twice except one. Pairs sit at indices (even, odd) until the lone element shifts them; use that parity on pairs as the predicate to binary-search the break.

Search in a Sorted Array of Unknown Size — no length is given. First double an exponential bound until it overshoots the target, then binary-search the bracketed range. Still O(log n).

Key takeaways

• Pick the predicate first. Binary search is "discard the impossible half"; the hard part is the yes/no test at mid, not the loop.
• Boundaries need two searches. First and last position are two biased binary searches, not one.
• In a rotated array one half is always sorted. Identify it by comparing mid to an endpoint, then test containment.
• Search on a property, not just a value. Parity, neighbour comparison, or an exponential bound can all serve as the splitting rule.
• Why this chapter matters: it builds the binary-search instinct — invariant, predicate, half-discard — that every later chapter reuses.