学步园

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4
5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

二分查找实现：

class Solution {
public:
    int binarySearch(vector<int> &num, int begin, int end)
{
	if(begin == end) return num[begin];
	if(num[begin] < num[end]) return num[begin];
	else
	{
		int mid = (end - begin)/2 + begin;
		if(num[begin] < num[mid]) return binarySearch(num, mid+1, end);
		else if(num[begin] > num[mid]) return binarySearch(num, begin, mid);
		else return num[begin] < num[end] ? num[begin] : num[end];
	}
}

int findMin(vector<int> &num) {
        return binarySearch(num, 0, num.size()-1);
    }
};

本题没有考虑有重复元素的情况，如果有重复的元素，就会在比较时总是出现相等而无法判断在哪被掰弯的了。/笑

那样的话难度会增加不少，最差就可以考虑O(n)过一遍了。