旋转数组的最小数字

题目链接: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

image.png

思路解题

1. 暴力解决，直接迭代遍历判断。不写代码了
   复杂度分析
   时间复杂度：O(N)。
   空间复杂度：O(1)。

2. 二分查找

   
   image.png

从图可以知道分为几种情况:
a. 如果中间值大于右边值，那么最小值在中间值和右边值之间 [m+1,r]
b. 如果中间值小于右边值，那么最小值应该在左边值和中间值之间 [l,m]
c. 如果中间值和右边值相等，那么最小值应该在左边值和右边值之间[l,r]

public int minArray(int[] numbers) {
        int l = 0,r = numbers.length-1;
        while ( l< r) {
            int m = (l + r) / 2;
            if (numbers[m] > numbers[r]) { // 如果中间值大于右边值，那么最小值在中间值和右边值之间 [m+1,r]，
                l = m + 1;
            }else if (numbers[m] < numbers[r]) { //如果中间值小于右边值，那么最小值应该在左边值和中间值之间 [l,m]
                r = m;
            }else { //中间值和右边值相等 那么最小值应该在左边值和右边值之间[l,r]
                int x = l;
                for (int k = l+1 ; k < r ; k++){
                    if (numbers[k] < numbers[x]){
                        x = k;
                    }
                }
                return numbers[x];
            }
        }
        return numbers[l];
    }

复杂度分析
时间复杂度：O(logN)。
空间复杂度：O(1)。