Skip to interview prep
Apexed

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.

An array first strictly increases and then strictly decreases (bitonic). Find the peak, and then search for a key. — Data structures & algorithms interview ques