剑指offer - 旋转数组的最小数字(Java实现)

题目链接：https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&&tqId=11159&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：直接遍历这个数组，找到数组最小值。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int n = array.length, ans = array[0];
        for(int i = 1; i < n; ++ i) {
            if(ans > array[i]) ans = array[i];
        }
        return ans;
    }
}

  思路二：使用二分的方法找到小于第一个数字的值，如果没有当前第一个数字就是最小值。如果一个非递减的数组经过了旋转，那么最左边的数字一定大于最右边的数字，设置两个指针 l 和 r，我们来判断 mid 和 array[0] 的关系，若是 array[0] > array[mid]，说明最小值可能还在左边，若是 array[0] < array[mid]，说明当前值可能是最小值，记录下来，然后去 mid 前面找还有没有更小的值，若是 array[0] == array[mid]，则 l 指针前移，如果每次判断都相等则这个程序有可能退化成 O(n) 的复杂度。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0) return 0;
        int l = 0, r = array.length - 1, target = array[0], ans = array[0];
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(array[mid] > target) {
                l = mid + 1;
            } else if(array[mid] < target) {
                r = mid - 1;
                ans = array[mid];
            } else {
                l ++;
            }
        }
        return ans;
    }
}