题解 | #旋转数组的最小数字#

#include <vector>
class Solution {
  public:
    int binSearch(vector<int>& nums, int start, int end) {
        // 1. 整段单调增
        if (nums[start] < nums[nums.size() - 1]) {
            return nums[start];
        } 
        // 2. 只有一个元素  
        else if (start == end) {
            return nums[start];
        }
        // 3. 目标：找比起始点和终止点都小的值
        else {
            // 中间点的值
            int mid = (start + end) / 2;
            // 最小值在中间点右侧
            if (nums[mid] > nums[start]) {
                start = mid + 1;
            }
            // 最小值在中间点左侧
            else if (nums[mid] < nums[start]) {
                end = mid;
            }
            else {
                // 关键，无法判断最小值在中间点左侧还是右侧，采取试探的办法
                start++;
                
            }
            return binSearch(nums, start, end);
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int minNumberInRotateArray(vector<int>& nums) {
        // write code here
        return binSearch(nums, 0, nums.size() - 1);
    }
};