二分搜索,和LeetCode 153. Find Minimum in Rotated Sorted Array相似。
只是在num[begin] == num[mid]时,,需要binary_search(++ begin, end, num); 这时仅将begin移进一位,并没有进行二分查找。
所以如测试用例为 num = {1, 1, 1, 1, 1, …, 1}等特殊情况时,最坏情况的时间复杂度为O(n).
代码:
class Solution {public:int findMin(vector<int> &num){return binary_search(0, num.size()-1, num);}private:int binary_search(int begin, int end, vector<int>& num){if (num[begin] < num[end] || end – begin <= 1){return min(num[begin], num[end]);} else if (num[begin] < num[(begin+end)>>1]){return binary_search(((begin+end)>>1)+1, end, num);} else if (num[begin] > num[(begin+end)>>1]){return binary_search(begin, (begin+end)>>1, num); } else{return binary_search(++begin, end, num);}}};
走自己的路,让别人说去吧