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

题目

image.png

解法

二分查找只能用在递增序列中，但是本题可以利用二分查找来缩减区间，不过需要注意比较对象。中点的值与左端点的值进行比较时，无法进行范围的缩减，需要与右端点进行比较：

  • 中点值比右端点大，则很明显，目标值在中点右半部分（不包括端点），左端点位置为中点位置 + 1
  • 中点值比右端点小，则很明显，目标值在中点左半部分（有可能就在端点处），因此右端点位置移至中点位置
  • 中点值与右端点一致，则无法确定目标值位置，缩减右半部分区间
    1. class Solution {
    2.   public int minArray(int[] numbers) {
    3.       int left = 0;
    4.       int right = numbers.length - 1;
    5.       while (left < right) {
    6.           int mid = (left + right) >> 1;
    7.           if (numbers[mid] > numbers[right]) {
    8.               left = mid + 1;
    9.           } else if (numbers[mid] < numbers[right]) {
    10.               right = mid;
    11.           } else {
    12.               // 当numbers[mid]==numbers[right]时，无法进行判断
    13.               right--;
    14.           }
    15.       }
    16.       return numbers[right];
    17.   }
    18. }