162. Find Peak Element.md

Solution1

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

note

• Binary search approach. The idea is to compare nums[mid] to its neighbor, either nums[mid - 1] or nums[mid + 1] because we keep our condition as lo + 1 < hi, so there are always two neighbors besides our mid value, otherwise it will exit out the loop. So, if the mid value is strictly less than its one side, we move the pointer to that side, otherwise, set the other end pointer to mid. Be careful that we only set the other pointer to mid instead of incrementing or decrementing by 1 because this point might potentially be our result.