How do you search a bitonic array — samples that rise then fall — for a target in O(log n)?

## What bitonic means A series is bitonic when it increases up to some index and decreases from there on — a single hump. A rocket's velocity samples from ignition through burnout and into drag-limited descent are the archetype. Either monotone piece may be empty, so a purely rising or purely falling series counts as a degenerate bitonic one, and the apex sits at an end. The array is emphatically **not** sorted; a plain binary search for a value will happily walk off toward the wrong slope and report a miss on data that contains the target. ## Stage one: locate the apex Use the slope comparison from peak finding, unchanged: ``` lo = 0 hi = length(a) - 1 while lo < hi: mid = floor((lo + hi) / 2) if a[mid] < a[mid + 1]: lo = mid + 1 else: hi = mid apex = lo ``` This is O(log n). The subtle point worth saying out loud in an interview: peak finding promises only *some* local maximum, which is normally a weaker guarantee than "the maximum". On a strictly bitonic profile the two coincide, because such a profile has exactly one local maximum by construction. The bitonic precondition is what upgrades the answer, not the algorithm. ## Stage two: two directional searches The rising side `[0, apex]` is sorted ascending and the falling side `[apex, n-1]` is sorted descending. Run one ordinary binary search on each, with the comparison flipped in the descending one: there, a probe value greater than the target means the target lies to the *right*, not the left. Return the first hit. Including `apex` in both ranges is harmless; excluding it from both is the off-by-one that makes the apex value itself unfindable, and it is the bug this decomposition most often ships with. ## The cost accounting Three logarithmic passes run one after another, so the costs **add**: O(log n) + O(log n) + O(log n) = O(log n). The frequent wrong answer is O(log² n), which would be right if the searches were *nested* — one running inside each step of another — and they are not. Space is O(1) beyond the input in iterative form. If all you need is the maximum value rather than membership of a target, stage one alone answers it and the other two passes are dead work. ## Degenerate and hostile inputs - **Monotone input.** If the samples only rise, the apex is the last index and the descending side is empty. The implementation must tolerate an empty range rather than assuming both sides are non-trivial. - **Equal adjacent samples.** A flat run — a plateau at the apex, or a held velocity during a coast phase — breaks the strictness the decomposition relies on. The probe `a[mid] < a[mid+1]` reads level and steers left, but level is genuinely ambiguous: the apex could be on either side. In the worst case you lose the halving argument and slide toward an O(n) scan. This is the same failure mode that duplicates inflict on other almost-sorted binary searches, and the honest interview answer is to state the precondition ("strictly bitonic, no equal adjacent readings") rather than to pretend the log bound survives. - **Input that is not bitonic at all.** Nothing in the method detects that. Fed a multi-humped profile it returns a confident wrong answer, so validating or guaranteeing the shape upstream is part of using it. Verifying bitonicity costs O(n), which defeats the purpose if you do it per query — do it once at ingest, or derive it from the physics of how the data is produced. ## Why this is worth knowing beyond the trivia The reusable idea is **decomposition into monotone pieces**: when a series is not sorted but is built from a small, known number of sorted runs, find the seams in logarithmic time and then search each run normally. The bitonic case is the two-run instance. Recognising it stops candidates from either giving up on logarithmic search entirely or, worse, running a plain binary search on data whose precondition it silently violates.