33.md

33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

分析阶段

把一个有序数组旋转后，在旋转后的数组中找到目标值的下标。

1、问题类型

问题属于“第一类：对某种数据结构及算法的应用”：

数据类型：数组

算法：查找算法

2、解题思路

从一个有序数组，旋转后称为两个有序数组，如下图所示：

在有序数组中查找目标值，一般使用“二分查找”。在一个有序数组中使用“二分查找”，是通过比较$nums[mid]$与$target$之间的关系，确定向左半部分或右半部分查找。

因此，在这个问题中首先要确定的就是当前$mid$是在左半边的数组还是在右半边，如下图中的两条黑线：

怎么确定$mid$是在左半边还是右半边？

根据有序数组的特点，右半边数组的最大值小于左半边数组的最小值，所以通过下面办法确定$mid$的位置：

• 如果$nums[mid]> nums[left]$，就表示在左半边

• 如果$nums[mid]< nums[right]$，就表示在右半边

确定了$mid$所在位置，怎么确定下一步向哪边移动查找？

与一般的“二分查找”相似，根据$target$与$nums[mid]$的关系来确定向左还是向右，另外，因为这里有两个有序数组，还要考虑$target$e与两个数组边界的关系，各个关系如下图所示：

• $nums[mid]&gt; nums[left]$，$mid$在左半边数组

① $target &lt; nums[mid] , target &gt;= nums[left]$ --> $right = mid - 1$

② $target &gt; nums[mid]$ --> $left = mid + 1$

④ $target &lt; nums[left]$ --> $right= mid - 1$

• $nums[mid]&lt; nums[right]$，$mid$在右半边

③ $target &lt; nums[mid]$ --> $right = mid -1$

④ $target &gt; nums[mid], target &lt;= nums[right]$ --> $left = mid +1$

③ $target &gt; nums[right]$ --> $right = mid -1$

根据上述过程，进行编码，验证上述过程是否正确。

编码阶段

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = (right - left) / 2 + left;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < nums[right]) {
            // 这里的 target 要 <= nums[right]，不能只是 <
            if (target <= nums[right] && target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        } else {
            // 这里的 target 要 >= nums[right]，不能只是 >
            if (target < nums[mid] && target >= nums[left]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }
    return -1;
}

时间复杂度：$O(N)$

总结阶段

针对“有序数组、查找”这类的关键字，第一反应是使用“二分查找”，关键是要确定下一个查找的方向和边界条件。

刚开始实现时，虽然分析阶段没有问题，但是在编码阶段判断边界条件时缺少了等号，导致一直不通过。