281. An array first strictly increases and then strictly decreases (bitonic). Find the peak, and then search for a key.
MediumSearching & selection
Technical
Show model answer
Binary search for the peak: at mid, if `a[mid] < a[mid + 1]` the peak is to the right, otherwise it is at mid or to the left. This finds the turning point in O(log n) instead of a linear scan.
To search for a key, find the peak, then binary search the increasing part normally and the decreasing part with reversed comparisons, for O(log n) total. If duplicates are allowed at the plateau, the O(log n) guarantee no longer holds in the worst case.