33. Search in Rotated Sorted Array
虽然题目要求时间复杂度是O(logn)，但发现直接线性查找和二分查找的时间差不多。。。不过我们也要用二分啊(^▽^)
思路其实很简单，和平时的二分几乎没区别，但是注意边界条件。假设左边界为left，右边界为right，中点为mid：
- 如果
target == nums[mid]，那直接返回结果； - 如果
nums[left] <= nums[mid]，那说明从left到mid全是递增序列，再判断target < nums[mid] && target >= nums[left]即target是否在该区间内，在该区间则直接二分查找该区间，不是的话就重新查找另一个区间； - 如果
left到mid不是递增序列，说明存在旋转点在left到mid之间，这样我们再看看mid到right是不是符合（2）中的条件，再按同样的方法处理；
代码如下：
class Solution {
public:
int search(vector<int> &nums, int target) {
int left = 0, right = nums.size() - 1;
int mid = (left + right) / 2;
while (left <= right) {
mid = (left + right) / 2;
if (target == nums[mid])
return mid;
if (nums[left] <= nums[mid]) {
if (target < nums[mid] && target >= nums[left])
right = mid - 1;
else
left = mid + 1;
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else
right = mid - 1;
}
}
return -1;
}
};
