方法一：先找到旋转点，然后根据目标值重新确定二分查找区域。
时间复杂度：用到两次二分查找，每次二分查找粗略的认为是O(logn)，那么时间复杂度为2 * O(logn)；
空间复杂度：O(1)。
int search(vector<int>& nums, int target) {
if (!nums.size()) return -;
int low = , high = nums.size() - , mid;
int rotate = ; //旋转点
//第一步先找到旋转点
if (nums[low] <= nums[high]) rotate = ; //无旋转
else
{
while (low < high)
{
mid = low + ((high - low) >> );
if (nums[mid] > nums[mid + ]) break;
if (nums[mid] >= nums[low]) low = mid;
else high = mid;
}
rotate = mid + ;
}
//重新规划二分查找区域
if (!rotate)
{
low = ;
high = nums.size() - ;
}
else
{
if (nums[] == target) return ;
else if (nums[] > target)
{
low = rotate;
high = nums.size() - ;
}
else
{
low = ;
high = rotate - ;
}
}
//二分查找
while (low <= high)
{
mid = low + ((high - low) >> );
if (nums[mid] == target) return mid;
else if (nums[mid] > target) high = mid - ;
else low = mid + ;
}
return -;
}
方法二：根据中间点和其他条件来调整上下边界。其实一开始就想的这个办法，但是写的过程中发现很混乱，所以就写了上一种比较清晰的方法。这个方法的关键是确定哪半边是有序的，在这个前提下分情况讨论会很清晰。
时间复杂度：O(logn)，空间复杂度：O(1)。
int search(vector<int>& nums, int target) {
if (!nums.size()) return -; //数组为空
int low = , high = nums.size() - , mid;
if (nums[low] <= nums[high]) //数组无旋转点，即升序排列
{
while (low <= high)
{
mid = low + ((high - low) >> );
if (nums[mid] == target) return mid;
else if (nums[mid] > target) high = mid - ;
else low = mid + ;
}
return -;
}
else //数组有旋转点
{
while (low <= high)
{
mid = low + ((high - low) >> );
if (nums[mid] == target) return mid;
if (nums[mid] > nums[low]) //左半边有序
{
if (nums[low] < target && nums[mid] > target) high = mid - ;
else if (nums[low] == target) return low;
else low = mid + ;
}
else //右半边有序
{
if (nums[high] > target && nums[mid] < target) low = mid + ;
else if (nums[high] == target) return high;
else high = mid - ;
}
}
return -;
}
}
总结：1）分析时把握问题的特征，不要没有头绪的想，不然就是猜了；
2）O(logn)复杂度是非常优秀的时间复杂度。