二分法查找旋转数组中最小的元素

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0)
            return 0;
        int low = 0;
        int high = array.length - 1;
        int mid = 0;
        while(low < high){
            //子数组是非递减的数组，如10111
            if(array[low] < array[high])
                return array[low];
            mid = low + (high - low) / 2;
            //说明low到mid之间是递增的，后面有可能是更小的数字
            if(array[mid] > array[low])
                low = mid + 1;
            //说明这时候是递增的，mid就是最小的元素
            else if(array[mid] < array[high])
                high = mid;
            //逼近high，退出循环
            else low++;
        }
        return array[low];
    }
}

旋转数组的目标元素

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid = 0;
        while(left <= right){
            mid = left + ((right - left) >> 1);
            //先让mid跟target比较
            if(nums[mid] == target){
                return mid;
            }
            //如果left -> mid 是递增
            if(nums[mid] >= nums[left]){
                //target在左半段  left -> mid
                if(target >= nums[left] && target < nums[mid]){
                    right = mid - 1;
                }else{  //target在右半段   mid -> right
                    left = mid + 1;
                }
            }else{  //left -> mid 不是递增  但是mid -> right 一定是递增的
                //target在右半段  mid -> right
                if(target <= nums[right] && target > nums[mid]){
                    left = mid + 1;
                }else{  //target在左半段  left -> mid
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}