問題

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
nums[i] != nums[i + 1] for all valid i.

方法

バイナリサーチを使ってピークに接近する。
O(logn)を強調した時点から配列をO(n)で巡回してピークを探してはいけないことをおぼえておこ

最初はバイナリサーチでpivotの右と左を同時に確認しようとしたが、pivotを基準にして上がる方向にだけ確認すればもっと最適の性能を出すのを気ついた。

１。pivotを基準にして、両方チェックする方法

function binarySearch (arr, left, right)

	pivot = (left + right) / 2
    
    if arr[pivot] is peak then
    	return pivot
    endif
    
    if left is not right then
    	
        leftResult = binarySearch(arr, left, pivot)
        rightResult = binarySearch(arr, pivot+1, right)
        
        if leftResult or rightResult is not -1 then
        	return result which is not -1
        endif
    endif
    
    return -1

endfunction

２。pivotを基準にして、pivotより数値が上がる方向を探して、ピークの範囲を狭せる方法

while left < right

	pivot = (left + right) / 2
    
    if arr[pivot] < arr[pivot+1] then
    	left = pivot + 1
    else
    	right = pivot
    endif
endwhile

return left

具現 (Java)

１。pivotを基準にして、両方チェックする方法

class Solution {
        
    private boolean isPeak(int[] nums, int pivot) {
        
        if (pivot == 0) return nums[0] > nums[1];

        if (pivot == (nums.length-1)) return nums[pivot-1] < nums[pivot];
        
        return nums[pivot-1] < nums[pivot] && nums[pivot] > nums[pivot+1];
    }
    
    private int binarySearch(int[] nums, int l, int r) {
                
        int pivot = (l+r) / 2;
        
        if (isPeak(nums, pivot)) return pivot;
        
        if (l != r) {
            
            int result1 = binarySearch(nums, l, pivot);
            
            if (result1 != -1) return result1;
            
            int result2 = binarySearch(nums, pivot+1, r);
            
            if (result2 != -1) return result2;
        }
        
        return -1;
    }
    
    public int findPeakElement(int[] nums) {
        
        return nums.length == 1? 0: binarySearch(nums, 0, nums.length-1);
    }
}

２。pivotを基準にして、pivotより数値が上がる方向を探して、ピークの範囲を狭せる方法

class Solution {
    
    public int findPeakElement(int[] nums) {
        
        if (nums.length == 1) return 0;
        
        int l = 0, r = nums.length-1;
        
        while (l < r) {
            
            int pivot = (l+r) / 2;
            
            if (nums[pivot] < nums[pivot+1]) l = pivot+1;
            else r = pivot;
        }
        
        return l;
    }
}