搜索旋转排序数组，search in rotated sorted array

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

一、题目描述
给定一个按升序排列的整数数组 nums，数组中的值 互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= 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 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

题目类型：二分查找

二、题目样例
输入：nums = [4,5,6,7,0,1,2], target = 0

输出：4

说明：0 在 nums 中的下标为 4。

三、算法思路
本题考查二分查找的应用，数组经过旋转后有两种情况，如下所示：

假设有 nums = [1, 2, 3 4, 5, 6, 7, 8]

第一种情况：旋转后和没旋转一样。

例如： nums = [1, 2, 3 4, 5, 6, 7, 8]。

第二种情况：旋转后，分为两段单调递增的区间。

例如：nums = [ 6, 7, 8, 1, 2, 3, 4, 5 ]，两段分别为 6 -> 8 和 1 -> 5 。

其中，第一种情况完全符合二分算法，主要处理第二种情况。

第二种情况又可以分为两种情况，如下所示：

情况 1：nums[left] < nums[mid]

二分的时候 mid 在 A 段，那么， x 的值（题目中是 target）可能位于三个部分，如上图所示。这时候满足条件 nums[left] < nums[mid]，然后，分为 x 在 left 和 mid 中间是一种情况，其它是一种情况，分开处理即可。

情况 2 ：nums[left] > nums[mid]
 二分的时候 mid 在 B 段，那么，x 的值（题目中是 target）可能位于三个部分，如上图所示。这时候满足条件 nums[left] > nums[mid]，然后，分为  x  在 mid 和 left 中间是一种情况，其它是一种情况，分开处理即可。

四、代码实现

4.1 头文件

#include <iostream>
#include <vector>
using namespace std;

4.2 代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right) {
            int mid = left + (right - left)/2;
            if(nums[mid] == target) { // 查找到值
                return mid;
            } else if(nums[left] < nums[mid]) {
                if(nums[left] <= target && target < nums[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else if(nums[mid] < target && target < nums[left]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return -1;
    }
};

五、复杂度分析
5.1 时间复杂度
时间复杂度：O(logn)，二分查找的时间复杂度为 O(logn)，因为每次的查找为折半查找，所以时间复杂度为O(logn)。

5.2 空间复杂度
空间复杂度：O(1)，仅用到三个临时变量，可以忽略，所以空间复杂度为O(1)。

六、题目链接
力扣

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬