（java版剑指offer）JZ11 旋转数组的最小数字（两种方法）

//方法一:遍历数组法.
//时间复杂度：n
//空间复杂度：1
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
    //1、排除特殊情况
        if (array.length == 0) {
            return 0;
        }
        
        //2、两个两个比较，最后找出最小值
        int min = array[0];    //定义临时存放最小值的变量
        for (int i = 1; i < array.length; i++) {
            min = Math.min(min, array[i]);    //遍历寻找最小值
        }
        return min;
    }
}

//方法二：二分法
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
// 二分查找，逼近
// 解法就是不断挪动左右双指针，直到右指针等于左指针时结束查找，此时的左指针（或右指针）指向的数便是数组最小值。
        //1、中间指针的值小于右指针，min在左部分（包括中间指针），将右指针替换中间指针，不能移动中间指针，避免中间指针是最小值
        //2、中间指针的值大于右指针，min在右部分，中间指针右移一位赋给左指针
        //3、中间指针的值等于右指针，右指针左移一位
        
        // 如果数组无元素，那么返回0
        if (array.length <= 0)
            return 0;
        // 定义左边界
        int left = 0;
        // 定义右边界-----在二分查找中，左边界值一定小于或等于右边界值
        int right = array.length - 1;
        while (left < right){
            // 计算左右区间最中间的索引
            int mid = left + ((right - left)>>1);    //右移运算符，比除2运算要快
            // 如果中间的值小于右边的值，说明此时数组最小值在左半部，
            // 挪动右边界指针到中间索引，为了避免此时的中间索引值就是最小的值，所以mid不能够减1
            if (array[mid] < array[right]) {
                right = mid;
            }
            // 如果中间的值大于右边值，说明此时的最小值在右半部，挪动左边界指针到当前中间索引的后一个
            else if (array[mid] > array[right]) left = mid + 1;
            // 如果中间值与右边界值相同，那么挪动右边界向左靠一位，这样就可以在下次循环时重新计算出中间索引值
            else right--;
        }
        // 当左边界和右边界重合则说明找到最小值,夹逼
        return array[left];    //return array[right];
    }
}