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


  • 0
    N

    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;
    }

  • 0
    C

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


  • 0
    N

    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.


Log in to reply
 

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