[Leetcode] Search in Rotated Sorted Array

原题链接在此

Suppose an array sorted in ascending order 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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

可以利用二分查找的思路，达到O(logN)的时间复杂度。

这样排序的特点就是，存在一个最小值（比如上面例子里的0），这个最小值的左半部分的最小值（比如上面例子里的4），大于：这个最小值的右半部分（包括他本身）的最大值（比如上面例子里的2）。可以利用这一点来找这个最小值。

class Solution {public:	int search(vector<int>& nums, int target) {		int low = 0, high = nums.size() - 1;		int mid = 0;		while (low < high) {			mid = (low + high) / 2;			if (nums[mid] > nums[high])				low = mid + 1;			else				high = mid;		}		int smallest = low;		if (nums.size() == 0) {			return -1;		} else if (target >= nums[smallest] && target <= nums[nums.size() - 1]) {			low = smallest;			high = nums.size() - 1;		} else if (target >= nums[0] && target <= nums[smallest - 1]) {			low = 0;			high = smallest - 1;		} else {			return -1;		}		while (low <= high) {			mid = (low + high) / 2;			if (nums[mid] == target) return mid;			if (nums[mid] < target) low = mid + 1;			else high = mid - 1;		}		return -1;	}};