Leetcode.33 搜索旋转排序数组

题目链接

Leetcode.33 搜索旋转排序数组 mid

题目描述

整数数组 $nums$ 按升序排列，数组中的值 互不相同 。

在传递给函数之前，$nums$ 在预先未知的某个下标 $k（0\le 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$ 和一个整数 $t$ ，如果 $nums$ 中存在这个目标值 $t$，则返回它的下标，否则返回 $-1$ 。

你必须设计一个时间复杂度为 $O(logn)$ 的算法解决此问题。

示例 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 = [4,5,6,7,0,1,2], target = 3
输出：-1

提示：

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

解法：二分

$nums$ 是一个排好序的数组，将其 旋转 之后，它仍然满足 两段性。

我们让 $l=0,r=n-1,mid=(l+r)/2$。

1.如果此时 $[l,mid]$ 区间是是有序的：

• 如果 $t$ 在区间 $[l,mid]$ 的范围内，也就是 $nums[l]\le t\le nums[mid]$，那么就可以缩减 $r$，即 $r=mid$；
• 否则说明 $t$ 不在这个区间内，那么就可以收缩 $l$，即 $l=mid+1$；

2.如果此时 $[mid+1,r]$ 区间是有序的：

• 如果 $t$ 在区间 $[mid+1,r]$ 的范围内，也就是 $nums[mid+1]\le t\le nums[r]$，那么就可以缩减 $l$，即 $l=mid+1$；
• 否则说明 $t$ 不在这个区间内，那么就可以收缩 $r$，即 $r=mid$；

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

C++代码：

class Solution {
public:
    int search(vector<int>& nums, int t) {
        int n =  nums.size();
        int l = 0 ,  r = n - 1;

        while(l < r){
            int mid = (l + r) >> 1;
            //这里必须为 nums[l] <= nums[mid]
            //因为 mid 是下取整的
            //如果当 nums 中的元素只有两个是 ，例如 nums = [3,1] , t = 1
            //此时 nums[l] 和 nums[mid] 都是同一个元素 即 3
            //如果不这样做的话 ， 就会不满足这个判断进入到 else 的逻辑中 ， 此时就会得出一个错误的答案
            if(nums[l] <= nums[mid]){
                if(nums[l] <= t && t <= nums[mid]) r = mid;
                else l = mid + 1;
            }
            else{
                if(nums[mid] < t && t <= nums[r]) l = mid + 1;
                else r = mid;
            }
        }

        return nums[l] == t ? l : -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26