整数数组 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 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -10^4 <= target <= 10^4

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

思路

我们仍可以利用二分查找的思路解决此问题。

注意到原数组为有限制的有序数组（除了在某个点会突然下降外均为升序数组）。我们取区间中点为mid，然后在mid未命中target的情况下，只需考虑在什么条件下我们搜索前半区间[low, mid)，什么条件下搜索后半区间[mid+1, high)？注意这两种情况是对称的，所以我们在这里只考虑target位于[low, mid)的条件。

情况一：nums[low] < nums[mid]那么nums[low]到nums[mid]为有序数组，那么当nums[low] <= target < nums[mid]时我们应该在[low, mid)范围内查找target；

情况二：nums[mid] < nums[low]那么在区间[low, mid)的某个点处发生了下降（旋转），那么target要么小于nums[mid]，此时有target < nums[mid] < nums[low] 。或者target大于nums[mid]，那么有nums[mid] < nums[low] <= target。

根据上述两种情况，我们有三个不等式：

nums[low] <= target < nums[mid]
             target < nums[mid] < nums[low]
                      nums[mid] < nums[low] <= target

我们只需对三项进行判断：

  • nums[low] <= target)
  • target < nums[mid]
  • nums[mid] < nums[low]

现在我们想知道这三项中有哪两项为真（明显这三项不可能均为真或均为假（因为这三项可能已经包含了所有情况））。

所以我们现在只需要区别出这三项中有两项为真还是只有一项为真。

使用 “异或” 操作可以轻松的得到上述结果（两项为真时异或结果为假，一项为真时异或结果为真）。

class Solution {

    public int search(int[] nums, int target) {
        int low = 0, high = nums.length;
        while (low < high) {
            int mid = (low + high) >> 1;
            if (nums[mid] == target) return mid;
            else if ((nums[low] <= target) ^ (target < nums[mid]) ^ (nums[mid] < nums[low])) low = mid + 1;
            else high = mid;
        }
        return -1;
    }

}

复杂度

  • 时间复杂度：。

  • 空间复杂度：。