【33】搜索旋转排序数组

1. 题目描述

2. 题目链接

https://leetcode.cn/problems/search-in-rotated-sorted-array/

3. 思路

对于有序数组，可以使用二分查找的方法查找元素。但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，那我们还能进行二分查找吗？答案是可以的。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从这个位置分开以后数组变成了和两个部分，其中左边这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分查找的时候，查看以当前为分割位置分割出来的两个部分和哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出在不在这个部分：

• 如果恰好等于，则直接返回。

• 如果是有序数组，且的大小满足，则我们应该将搜索范围缩小至，否则在中寻找。

• 如果是有序数组，且的大小满足，则我们应该将搜索范围缩小至，否则在中寻找。

4. 代码实现

public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    if (nums.length == 1) {
        return nums[0] == target ? 0 : -1;
    }
    // 二分查找
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        // [left,mid]是有序数组
        if (nums[mid] >= nums[0]) {
            // 判断target是否在[left,mid-1]区间内
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // [mid+1,right]是有序数组
        else {
            // 判断target是否在[mid+1,right]区间内
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

• 时间复杂度：，其中为数组的大小。整个算法的时间复杂度即为二分查找的时间复杂度，即。
• 空间复杂度：。我们只需要常数级别的空间存放变量。