Find Peak Element

With nums[1]=nums[n]=, find an index let nums[i1]<nums[i] and nums[i+1]<nums[i]. Note that for any i, nums[i]nums[i+1]. A linear solution is simple, but we can solve this problem in O(logN). Make use of the conditions that nums[i]nums[i+1], we take a iteration way that is very similar to binary search. For an index i, we search peak element in the left side of it if nums[i1]>nums[i], conversely, we search peak element in the right side.

To prove this algorithm is simple. If nums[i1]>nums[i], as each adjoined element is different, there must be a 1j<i1 that let nums[j]<nums[i], so there must be a peek element in the range of [0,i1). There are a similar conclusion if num[i+1]>nums[i] and in the right side.

public class FindPeakElement {

    public int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int mid;

        while(true) {
            mid = (l + r) / 2;
            if (mid - 1 >= 0 && nums[mid - 1] > nums[mid]) {
                r = mid - 1;
            } else if (mid + 1 < nums.length && nums[mid + 1] > nums[mid]) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
    }
}