#局部最小

定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果
arr[0]<arr[1]，那么arr[0]是局部最小；如果arr[N-1]<arr[N-2]，那么arr[N-1]是局部
最小；如果0<i<N-1，既有arr[i]<arr[i-1]又有arr[i]<arr[i+1]，那么arr[i]是局部最小。
给定无序数组arr，已知arr中任意两个相邻的数都不相等，写一个函数，只需返回arr中任
意一个局部最小出现的位置即可。

思路

比较图
比较图

如图所示，当不满足arr[0]和arr[n-1]是局部最小时，必有arr[0]>arr[1]和arr[N-2]<arr[N-1]
因此其中必有局部最小

对于任意位置k，0<k<N-1

若arr[k] > arr[k+1],结合arr[N-2]<arr[N-1]则在k+1到n-2位置必有局部最小

若arr[k-1] < arr[k],结合则arr[0]>arr[1]在1到k-1位置必有局部最小

因此便可以用二分解出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int find(int []a){
		if(a[0] < a[1] || a.length == 1){
			return 0;
		}else if(a[a.length-2] > a[a.length-1]){
			return a.length-1;
		}else{
			int mid = 0;
			int left = 1;
			int right = a.length-2;
			while(left < right){
				mid = (left + right)/2;
				if(a[mid-1] < a[mid]){
					right = mid-1;
				}else if(a[mid] > a[mid+1]){
					left = mid+1;
				}else{
					//m-1>=m<=m+1,显然m是局部最小
					return mid;
				}
			}
			//return left是什么鬼？！
			return mid;
		}
}