33. 搜索旋转排序数组 - 力扣（LeetCode）

发表于 更新于 分类于 阅读次数： Disqus：

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。 示例 1: 输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4 示例 2: 输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1

题解

看到题目要求的复杂度为[latex] o(log_2n) [/latex],首先想到的二分查找法，但一般的适用场景是整体有序，对于这种情况，如果我们能确定旋转位置rotate_idx，则整个序列分成两部分：[0, rotate_idx)和[rotate_idx, nums.size())。当target >= nums[0]时target只可能出现前一部分，反之，则出现后一部分。 如何确定rotate_idx？借鉴官方题解，这里也采用二分法。 [0, rotate_idx)和[rotate_idx, nums.size())有以下特点： [latex] \\begin {split} nums[0] < nums[1] < \\cdots< nums[rotate\\_idx - 1] > \\\\ nums[rotate\\_idx] <\\cdots nums[rotate_idx]即可。 具体二分的方式查看代码。

代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //第一步：寻找旋转点,最小元素的下标
        int beg = 0, end = nums.size() - 1, mid = (beg + end) / 2;
        int rotate_index = 0;
        if(nums.size() == 0){//特殊情况
            return -1;
        }
        while(beg <= end){
            mid = (beg + end) / 2;
            if(mid < nums.size() - 1 && nums[mid] > nums[mid + 1]){
                rotate_index = mid + 1;
                break;
            }
            else if(nums[mid] >= nums[beg]){//搜索右边序列
                beg = mid + 1;
            }
            else{//搜索左边序列
                end = mid - 1;
            }
        }
        //第二步：确认target会出现在哪个区域[0, rotate_index)或[rotate_index, nums.size())
        if(target >= nums[0]){//目标值大于nums[0]，左边查找
            beg = 0, end = (rotate_index == 0?nums.size() - 1:rotate_index - 1);  
        }
        else{
            beg = rotate_index;
            end = nums.size() - 1;
        }
        while(beg <= end){//第三步：二分查找目标值
            mid = (beg + end) / 2;
            if(nums[mid] > target){
                end = mid - 1;
            }
            else if(nums[mid] < target){
                beg = mid + 1;
            }
            else{
                return mid;
            }
        }
        if(beg > end){
            return -1;
        }
        else{
            return 0;
        }
    }
};

执行结果