# C++ binary search solution, but why binary search works?

• Leetcode requires logarithmic complexity, so one would naturally consider using binary search. But how to prove it?

``````int findPeakElement(vector<int>& nums) {
int sz = nums.size();
int low = 0, high = sz-1;
while(low < high) {
int mid = (low+high)>>1;
if(mid+1 < sz && nums[mid] < nums[mid+1])    low = mid+1;
else if(mid >= 1 && nums[mid] < nums[mid-1])   high = mid;
else return mid;
}
return low;
}``````

• You can prove it using invariants. If you want, you can take a look at my post explaining this solution: Solution using invariants

• First of all thanks for your answer! I think binary search works because of the assumption "num[-1] = num[n] = -∞" - either the sequence goes up and down and you can find a peak in the middle; or the sequence strictly and monotonically increases/decreases, then you end up with a peak at the end/front if we assume "num[-1] = num[n] = -∞". But suppose I don't have this assumption, it looks like there is no logarithmic solution?! Also, binary search will land on a peak for this question, but I don't know which peak it will land on - for example, the first or the last peak.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.