Clean Java binary search solution


  • 0
    Y

    The trick of this problem is to keep two elements during the binary search, this way during the search, the index mid-1 and mid+1 will always be valid. To do so, we need to only start binary search when start+1<end, to make sure we have 3 numbers to begin with.

    As for the if branch statement, a trick works for me is to think about the mid falls in a bottom point. Then if nums[mid] < nums[mid-1], we need to search left, if nums[mid] < nums[mid+1], search right. Otherwise, the mid will be a peak. I hope it helps.

    public class Solution {
        public int findPeakElement(int[] nums) {
            int start = 0;
            int end = nums.length - 1;
            while(start + 1 < end) {
                int mid = start + (end - start) / 2;
                if(nums[mid] < nums[mid-1]) {
                    end = mid;
                } else if(nums[mid] < nums[mid+1]) {
                    start = mid;
                } else {
                    return mid;
                }
            }
            return nums[start] >= nums[end] ? start : end;
        }
    }
    

Log in to reply
 

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