Find Peak Element

Find peak element returns the index of any element strictly greater than both neighbours, in O(log n). That an unsorted array admits a logarithmic search is the surprising part, and the reason is worth understanding. Binary search normally needs sorted data. Here the enabling property is different — the problem states that nums[i] != nums[i+1] for all i, and that out-of-bounds neighbours count as negative infinity: - Comparing nums[mid] with nums[mid + 1] reveals a slope, and a slope always leads to a peak in that direction. If nums[mid] < nums[mid + 1], the sequence is ascending at mid. Following it rightward, it either keeps rising until the array ends — where the boundary acts as negative infinity, making the last element a peak — or it turns downward at some point, which is a peak. Either way a peak exists to the right, so the left half can be discarded. If nums[mid] > nums[mid + 1], the same argument applies leftward, with mid itself still a candidate. That guarantee is what makes the halving valid without sorted input. The loop runs while left < right, and the descending case sets right = mid rather than mid - 1, since mid may be the peak. There is no equality case to handle, because adjacent elements are never equal. Any peak is acceptable, which is why finding a peak rather than the maximum is enough — and it is why the O(n) scan for the global maximum, while correct, does more work than asked.

Binary search without a sorted array. Comparing nums[mid] to its right neighbour tells you which side must contain a peak: if the slope rises, a peak exists to the right; if it falls, one exists at or left of mid. The out-of-bounds -∞ convention guarantees a peak always exists.