旋转数组的最小数字_JAVA_简单

• 原数组为非递减（递增/相等）排序，旋转后仍然部分有序，在其中查找，可使用二分法
• 正常二分法用中值与查找值比较，该题查找最小值，使用中值和左右某端比较，判断最小值在哪个区间
• 判断条件抉择要点：既要符合单段非递减排序的查找最小值，又要符合两段混合查找最小值——选择右端点为基准点
• 右大换右（非递减区间/混合区间），右小换左（混合区间），相等条件下则左移右端点一位
• 优化：右值大于左值则为非递减区间，可直接返回该区间左值

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        // 以右边为基准点，开始二分查找
        int start = 0, end = array.length - 1, mid;
        while(start < end) {
            // 已经找到了包含最小值的非递减区间
            if(array[start] < array[end]) {
                return array[start];
            }
            mid = (start + end) / 2;
            // 右边大则舍弃右边（非递减/混合区间）
            if(array[end] > array[mid]) {
                end = mid;
            // 右边小则舍弃左边（混合区间）
            } else if(array[end] < array[mid]) {
                start = mid + 1;
            // 相等则右边缩小
            } else {
                end--;
            }
        }

        // 存在为0处理
        return start == end ? array[start] : 0;
    }
}