LeetCode 153. Find Minimum in Rotated Sorted Array

二分查找。

因为在旋转前的数组是排好序了的,

所以当num[begin] > num[mid]时,表示我们要搜寻的最小数字在num[begin, …, mid]之间;

反之,num[begin] < num[mid]时,表示我们要搜寻的最小数字在num[mid+1, …, end]之间(没有被打乱的数组,如1,2,3,4,..,n这种情况除外,在下面代码中我们进行了特判)。

例:考虑num = {5, 6, 7, 1, 2, 3, 4},

begin = 0, end = 6, mid = 3

num[begin] = 5 > num[mid] = 1. 所以我们要搜寻的最小数字在num[0, 1, 2, 3]之间。

代码:

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, (begin+end)>>1, num);} else{return binary_search(((begin+end)>>1)+1, end, num);}}};

,世界上那些最容易的事情中,拖延时间最不费力。

LeetCode 153. Find Minimum in Rotated Sorted Array

相关文章:

你感兴趣的文章:

标签云: