LeetCode -- Find Peak Element

LeetCode -- Find Peak Element

題目描述：


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


Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.


The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.


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


For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.


在一個序列中，找到nums[i] > nums[i-1] && nums[i] > nums[i+1]的索引i。
本題可以理解為在1個不連續的點集中，找到極大值點（先增後減）。


本題是一個典型的二分法查詢問題：


1.如果序列本身是遞減，nums[0]就是極大值點。
2.如果序列末尾處遞增，nums[len -1]就是極大值點。
3.如果nums[i] > nums[i+1] 且 nums[i] > nums[i-1]，那麼nums[i]就是極大值。
4.如果序列在nums[i]處遞增，即nums[i-1] < nums[i] < nums[i+1]，那麼右邊一定存在極大值。
5.如果序列在nums[i]處遞減，即nums[i-1] > nums[i] > nums[i+1]，左邊一定存在極大值。




實現代碼：

public class Solution {
    public int FindPeakElement(int[] nums) {
        if(nums.Length == 0){
			return -1;
		}
		if(nums.Length == 1){
			return 0;
		}
		if(nums.Length == 2){
			return nums[0] > nums[1] ? 0 : 1;
		}
		if(nums[nums.Length - 1] > nums[nums.Length - 2]){
			return nums.Length -1;
		}
		if(nums[0] > nums[1]){
			return 0;
		}
		
		var l = 0;
		var r = nums.Length - 1;
		while(l < r - 1){
			var m = (l + r) / 2;
			
			if(nums[m] > nums[m-1] && nums[m] > nums[m+1]){
				return m;
			}
			else if(nums[m] > nums[m-1] && nums[m] < nums[m+1]){ // increasing , go right
				l = m;
			}
			else { // decreasing , go left
				r = m;
			}
		}
		
		return -1;
    }
}