demo17.txt

package chapter8;

//在数组中找到一个局部最小的位置
public class demo17 {

	/**
	  这个最小值并不是唯一的，只要符合要求即可.
	  主要是为了练习二分法
	 */
	public static void main(String[] args) {
		int[] arr = {1,0};
		int[] arr1 = {0,1};
		int[] arr2 = {0,1,9,3};
		int res2 = findMin(arr2);
		int res = findMin(arr);
		int res1 = findMin(arr1);
		System.out.println(res+" "+res1+" "+res2);
	}

	public static int findMin(int[] arr){
		if(arr==null || arr.length==0){
			return -1;
		}
		if(arr.length==1){
			return arr[0];
		}
		if(arr[1]>arr[0]){
			return arr[0];
		}
		if(arr[arr.length-2]>arr[arr.length-1]){
			return arr[arr.length-1];
		}
		//用二分法来处理，找这个局部最小值，二分法不一定要用在有序数组中
		int left = 1, right = arr.length-2,mid = 0;
		while(left<right){
			mid = (left+right)/2;
			if(arr[mid-1]>arr[mid]){
				right = mid-1;
			}
			else if(arr[mid+1]<arr[mid]){
				left = mid+1;
			}
			else{
				return mid;
			}
		}
		return left;
		
	}
	
}