Find Peak Element is a favorite interview question because it breaks a rule most candidates have memorized: "binary search needs a sorted array." The array here is not sorted, yet the expected answer runs in O(log n). If you can explain why, you show the interviewer you understand binary search as a technique for shrinking a search space, not just a trick for sorted lists.
You get an array nums where no two neighbors are equal. A peak is an element strictly greater than its neighbors. Treat nums[-1] and nums[n] as negative infinity. Return the index of any peak.
Walk left to right and return the first i where nums[i] > nums[i+1]. If you never find one, the last index is a peak. This is O(n) and correct, and stating it in one sentence buys you credibility before you optimize.
def find_peak_linear(nums):
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return i
return len(nums) - 1
Look at any middle index mid and compare it with mid + 1.
nums[mid] < nums[mid + 1], you are on an uphill slope. Keep walking right and the values either keep rising until the end (and the last element is a peak, because the boundary is negative infinity) or they drop at some point (and the top of that climb is a peak). Either way, a peak exists to the right of mid.nums[mid] > nums[mid + 1], you are on a downhill slope, and by the mirror argument a peak exists at mid or to its left.That is the whole invariant: the current window always contains at least one peak. Every comparison throws away half the window while keeping that promise true.
def find_peak(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # peak is to the right
else:
hi = mid # mid could be the peak
return lo
Notice two details interviewers watch for. First, the loop is lo < hi, not lo <= hi, so mid + 1 is always in range. Second, the else branch sets hi = mid, not mid - 1, because mid itself might be the answer. When lo == hi, the window has one element and the invariant says it is a peak.
lo < hi and hi = mid choices.[1, 2, 3, 1] (returns 2) and [1, 2, 1, 3, 5, 6, 4] (returns 1 or 5, both valid).[1, 1, 1, 2, 1, 1], and the worst case becomes O(n).The pattern to remember is "binary search on a monotonic property," and it shows up again in Search in Rotated Sorted Array, Koko Eating Bananas and minimum-capacity problems.
Disclosure: I work on Linkjob AI. If you want live practice talking through problems like this, you can try it free.