Sharing a more standard Binary Search C++ Solution


  • 19
    class Solution {
    public:
        int findPeakElement(const vector<int> &num) {
            int low = 0, high = num.size() - 1;
            while (low < high - 1) {
                int mid = (low + high) / 2;
                if (num[mid] > num[mid - 1] && num[mid] > num[mid + 1]) 
                    return mid;
                else if (num[mid] > num[mid + 1]) 
                        high = mid - 1;
                     else 
                        low = mid + 1;    
            }
            return num[low] > num[high] ? low : high;
        }
    };

  • 4
    X

    I don't understand why your solution is correct (although it is accepted by the oj system). Try this test case:
    num = {1, 2, 1, 1, 1, 1};
    The correct answer should be 1, while your solution gives 5.


  • 2

    First, this case {1, 2, 1, 1, 1, 1} is not RIGHT. It does NOT satisfy "Given an input array where num[i] ≠ num[i+1]" , and with that requirement together with this "num[n] & num[-1] = -∞", they're very important. They guarantee that the peak could always exist and then guarantee the correctness of binary search for this problem.


  • 0
    X

    Sorry, you are right. And your solution is excellent. I forget the condition that "num[i] ≠ num[i+1]".


  • 0

    Thank you :)


  • -1
    M

    i think this is wrong answer.
    for example:
    [1,9,2,3,4,5,6,7]
    your function will return 7,
    but the right answer is 9.


  • 1

    actually 7 is also a right answer:) you can read the question again~


  • 0
    M

    oh,you are right. (^__^)


  • 0
    Q
    This post is deleted!

  • 0
    T

    a more concise solution:

    int findPeakElement(vector<int>& nums) {
            int l = 0, r(nums.size());
            while(l < r){
                int mid = l + (r-l) / 2;
                if(mid == l) break;
                if(nums[mid] > nums[mid-1]) l = mid;
                else r = mid;
            }
            return l;
        }

  • 0
    M
    This post is deleted!

  • 0
    L

    @loli said in Sharing a more standard Binary Search C++ Solution:

        while (low < high - 1) {
    

    Why while (low < high - 1) { not while (low < high) ? Isn't the latter more standard for binary search problems?


Log in to reply
 

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