image.png

    1. 暴力解法直接使用for循环遍历，但是很明显不是面试官要的
    2. 使用二分查找法

    将数组的最右边的元素当作target进行比较
    当arr[mid] > target，此时很明显目标值在mid之后，并且不可能是arr[mid]，所以l=mid+1
    当arr[mid] < target，此时很明显目标值在mid之前，并且可能是arr[mid]，所以r = mid
    当arr[mid] = target，

    • 如果是 1 0 1 1 1， arr[mid] = target = 1, 显然答案在左边
    • 如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边
      所以这种情况，不能确定答案在左边还是右边，那么就让r =r - 1;慢慢缩少区间，同时也不会错过答案。
      1. public class Solution {
      2. public int minNumberInRotateArray(int [] array) {
      3.    if(array.length == 0)
      4.        return 0;
      5.    int l = 0, r = array.length-1;
      6.    while(l < r){
      7.        if(array[l] < array[r]){     //没有旋转或者理解为全部旋转，相当于原数组
      8.            return array[l];
      9.        }
      10.        int mid = l + (r-l)/2;
      11.        if(array[mid] < array[r]){
      12.            r = mid;
      13.        }else if(array[mid] > array[r]){
      14.            l = mid+1;
      15.        }else {
      16.            --r;
      17.        }
      18.    }
      19.    return array[l];
      20. }
      21. }
      **