leetcode 链接：搜索旋转排序数组

题目

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标（旋转后数组中的下标），否则返回 -1 。

进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

示例：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

输入：nums = [1], target = 0
输出：-1

解答 & 代码

二分法搜索，使用 mid 将数组分为左右两部分，至少有一个部分是有序的，根据有序的半边来判断将搜索范围放在左边还是右边

注意：

• 第 21 行的等号，否则对于输入 [3, 1], 1 过不了

• 并且注意用 nums[mid] 和 nums[left] 比大小来判定左半边是否有序，而不是用 nums[mid-1]，mid-1 可能小于 0

  class Solution {     
  public:
    int search(vector<int>& nums, int target) {
        int left = 0;                    // 左边界
        int right = nums.size() - 1;    // 右边界
  
        // 特殊情况
        if(right < 0)
            return -1;
        if(right == 0)
            return nums[0] == target ? 0 : -1;
  
        // 二分查找
        while(left <= right)
        {
            int mid = (left + right) / 2;
            // 如果 mid 的值就是 target，找到，返回其下标值 mid
            if(nums[mid] == target)
                return mid;
            // 如果左边部分是有序的（即 nums[left] <= nums[mid]）
            else if(nums[left] <= nums[mid])    // 注意这里的等号
            {
                // 并且 target 的大小在左边部分的左、右边界之间，则将搜索范围缩小为左边部分
                if(nums[left] <= target && target <= nums[mid])
                    right = mid - 1;
                // 否则到右边部分搜索
                else
                    left = mid + 1;
            }
            // 如果右边部分是有序的
            else
            {
                // 并且 target 的大小在右边部分的左、右边界之间，则将搜索范围缩小为右边部分
                if(nums[mid] <= target && target <= nums[right])
                    left = mid + 1;
                // 否则在左边部分搜索
                else
                    right = mid - 1;
            }
        }
        return -1;    // 不存在，返回 -1
    }
  };
  

  执行结果： ``` 执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 77.20% 的用户 内存消耗：10.7 MB, 在所有 C++ 提交中击败了 78.74% 的用户

上面的写法，对于等号、mid 等处理不甚明白，自己换了个思路：
```cpp
class Solution {     
public:
    int search(vector<int>& nums, int target) {
        int left = 0;                    // 左边界
        int right = nums.size() - 1;    // 右边界

        // 特殊情况
        if(right < 0)
            return -1;
        if(right == 0)
            return nums[0] == target ? 0 : -1;

        // 二分查找
        while(left <= right)
        {
            // 如果 mid 的值就是 target，说明找到，返回其下标值 mid
            int mid = (left + right) / 2;
            if(nums[mid] == target)
                return mid;

            // 如果左半部分不存在（即mid就是left） 
            // or 左半部分有序且target不在左半部分 
            // or 左半部分非有序(则右半部分必然有序)且target在右半部分
            // 则将查找范围缩小为右半部分
            if(mid - 1 < left || 
                (nums[left] <= nums[mid - 1] && (target < nums[left] || target > nums[mid - 1])) ||
                (nums[left] > nums[mid - 1] && (nums[mid] <= target && target <= nums[right])))
                left = mid + 1;
            // 否则将查找范围缩小到左半部分
            else
                right = mid - 1; 
        }
        return -1;
    }
};

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：10.8 MB, 在所有 C++ 提交中击败了 26.00% 的用户

递归解法：

class Solution {
private:
    int binarySearch(vector<int> nums, int target, int left, int right)
    {
        if(left > right)
            return -1;

        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid;

        if((nums[left] < nums[mid] && target >= nums[left] && target < nums[mid]) ||
            (nums[mid] < nums[right] && (target < nums[mid] || target > nums[right])))
            return binarySearch(nums, target, left, mid - 1);
        else
            return binarySearch(nums, target, mid + 1, right);
    }

public:
    int search(vector<int>& nums, int target) {
        return binarySearch(nums, target, 0, nums.size() - 1);
    }
};