本文最后更新于:2020年4月27日 下午

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

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [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

解题思路

这个题如果是已排序的数组,那么用二分查找应该就是最快的,但是题目是进行了旋转后的数组。

其实仔细观察不难发现,相当于题目已经把一个已排序的数组分成了两部分,前面一部分的数较大,后面一部分的数较小。以示例中的数组 [4,5,6,7,0,1,2] 为例,前一部分的数为 [4,5,6,7] ,后一部分的数为 [0,1,2] ,前面一部分任意一个数都是大于后面一部分的数的。

与标准二分查找不同的是,这个题的二分的点并不是数组的正中心,并且我们也不知道具体是从哪里二分的(需要遍历查找)。但是可以肯定的是,题目给出的 target 只可能属于两部分中的一个部分,换言之 target 要么大于数组的第一个数,要么小于数组的最后一个数。

那么剩下的事情就好办了,只需要遍历找出 target 的位置即可,当然这里并不能用到二分查找,因为没法确定边界的位置,对于前面一部分来说没法确定右边界的位置,而对于后面一部分来说,没法确定左边界的位置,当然也可以通过遍历找到边界的位置的,但是显然既然都要遍历数组了,不就可以直接进行逐个比较了吗。

首先判断 target 可能在前面一部分还是在后面一部分,如果在前面一部分则从前往后遍历,如果在后面一部分则从后往前遍历,找到了就跳出循环,返回结果。如果找不到函数返回默认值 -1

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int ans = -1;
        if (nums.empty()) return -1;
        if (target >= nums[0]) {
            //在前半部分找
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] == target) {
                    ans = i;
                    break;
                }
            }
        }
        else if (target <= nums.back()) {
            //在后半部分找
            for (int i = nums.size() - 1; i >= 0; i--) {
                if (nums[i] == target) {
                    ans = i;
                    break;
                }
            }
        }
        return ans;
    }
};