旋转数组最小数字

给定一个一个排序数组, 将前端部分数字放到数组尾部, 求出数组中的最小数字, [4,5,6,1,2,3] 返回1.

对于有序数组, 考虑使用二分查找法.

  • 当 arr[mid] > arr[high] 时, 最小值必在【mid+1, high】区间, 此时 low=mid+1
  • 当 arr[mid] < arr[high] 时, 最小值必在【low, mid】之间,此时 high=mid
  • 当arr【mid】==arr[high] 时, 此时出现重复数字, 将右区间左移1, high–

    int minReverseArr(vector<int> arr){
    int len = arr.size();
    if(len==1)
        return arr[0];
    int low=0;
    int high=len-1;
    while(low<high){
        int mid = (low + high)/2;
        if(arr[mid] > arr[high])
            low = mid +1;
        else{
            if(arr[mid] < arr[high])
                high=mid;
            else
                high--;
        } 
    }
    return arr[low];
    }