旋转数组最小数字

LeetCode

给定一个一个排序数组, 将前端部分数字放到数组尾部, 求出数组中的最小数字, [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];
}