0ms binary search solution in C with explanation


  • 0

    Using binary search.

    • if nums[mid] < nums[mid - 1], that means the peak is on the left of nums[mid], so we move high to mid - 1

    • if nums[mid] < nums[mid + 1], that means the peak is on the right of nums[mid], so we move low to mid + 1

    • otherwise nums[mid] is peak, just return mid.

    below is the code in C

    int findPeakElement(int* nums, int numsSize) {
        int low = 0, high = numsSize - 1, mid;
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (mid && nums[mid] < nums[mid - 1]) {
                high = mid - 1;
            } else if (mid + 1 < numsSize && nums[mid] < nums[mid + 1]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
    }
    

    in python

    class Solution(object):
        def findPeakElement(self, nums):
            low, high = 0, len(nums) - 1
            while low <= high:
                mid = (low + high) >> 1
                if mid and nums[mid] < nums[mid - 1]:
                    high = mid - 1
                elif mid + 1 < len(nums) and nums[mid] < nums[mid + 1]:
                    low = mid + 1
                else:
                    return mid

Log in to reply
 

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