6_4循环有序数组最小值

2017-10-05  本文已影响25人  X_Y

对于一个有序循环数组arr,返回arr中的最小值。有序循环数组是指,有序数组左边任意长度的部分放到右边去,右边的部分拿到左边来。比如数组[1,2,3,3,4],是有序循环数组,[4,1,2,3,3]也是。

给定数组arr及它的大小n,请返回最小值。

测试样例:
输入:[4,1,2,3,3],5
返回:1

class MinValue {
public:
    int getMin(vector<int> arr, int n) {
        // write code here
        if(n<1) return -1;
        int left = 0, right = n-1, res = 99999999, mid = 0;
        while(left < right){
            mid = left + (right - left) / 2;
            if(arr[mid] >= arr[right]){
                left = mid + 1;
                res = res < arr[right] ? res : arr[right];
            }else if(arr[mid] <= arr[left]){
                right = mid - 1;
                res = res < arr[mid] ? res : arr[mid];
            }else{
                return arr[left] < res ? arr[left] : res;
            }
        }
    return res;
    }
};
上一篇 下一篇

猜你喜欢

热点阅读