Array Binary Search

    Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. The array may contain duplicates. Example 1: Input: [1,3,5]

    Output: 1

    Example 2:

    Input: [2,2,2,0,1]

    Output: 0

    相似的题目
    Find Minimum in Rotated Sorted Array 中等

    1. 初始化下标 left 和 right
    2. 每次计算中间下标 mid = (right + left) / 2，这里的除法是取整运算，不能出现小数
    3. 当 numbers[mid] < numbers[right] 时，说明中点落在数组的前半部分，说明最小值在 [left, mid] 区间中，则令 right = mid，用于下一轮计算
    4. 当 numbers[mid] > numbers[right] 时，说明中点落在数组的前后部分，说明最小值在 [mid, right] 区间中，则令 left = mid + 1，用于下一轮计算
    5. 当 numbers[mid] == numbers[right] 时，无法判断最小值在哪个区间之中，此时让 right—，缩小区间范围，在下一轮进行判断
    • 为什么是 right— 缩小范围，而不是 left++？
      • 因为数组是升序的，所以最小值一定靠近左侧，而不是右侧
      • 比如，当存在 [1,2,2,2,2] 这种情况时，left = 0，right = 4，mid = 2，数值满足 numbers[mid] == numbers[right] 这个条件，如果 left++，则找不到最小值
        1. class Solution {
        2. public int findMin(int[] nums) {
        3.    int left = 0;
        4.    int right = nums.length - 1;
        5.    while (left <= right) { // 二分法中<=,<无所谓，最后返回时随机应变
        6.        int mid = left + (right - left) / 2;
        7.        if (nums[mid] < nums[right]) {
        8.            right = mid; // 该情况下mid可能是结果，所以不是mid-1
        9.        } else if (nums[mid] > nums[right]) {
        10.            left = mid + 1;
        11.        } else if (nums[mid] == nums[right]) {
        12.            right --;
        13.        }
        14.    }
        15.    return nums[left]; //因为只有right指针会有不安全的移动行为，所以返回时选择left
        16. }
        17. }