本文共 2959 字，大约阅读时间需要 9 分钟。

You are given an integer array nums sorted in ascending order, and an integer target .

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] ).

If target is found in the array return its index, otherwise, return -1 .

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3Output: -1

Example 3:

Input: nums = [1], target = 0Output: -1

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is guranteed to be rotated at some pivot.
• -10^4 <= target <= 10^4

题意：给出一个升序排序的数组和一个整数，这一数组在未知的某个点上进行了旋转，如 [1,2,3,4,5,6,7] 可能变为 [4,5,6,7,1,2,3] 。然后需要在数组中搜索目标值，如果存在则返回它的位置。

解法1 顺序搜索

完全没有利用到数组的特征，直接进行最简单的顺序搜索，$O(n)$ 的时间复杂度：

class Solution {
   public:    int search(vector
   
    & nums, int target) {
           for (int i = 0; i < nums.size(); ++i) if (nums[i] == target) return i;        return -1;    }};
   

效率如下，比较感人：

执行用时：16 ms, 在所有 C++ 提交中击败了17.24% 的用户内存消耗：11.3 MB, 在所有 C++ 提交中击败了5.21% 的用户

解法2 找到旋转点

我们可以找到那个旋转点，不是进行数组的恢复（太浪费时间了），而是经过判断，对旋转点的一边进行二分搜索，得到结果。这一算法的整体时间复杂度是 $O(n)$ ，没有实质的改进。暂时不想写代码。

解法3 利用数组的特征

对于旋转数组，如果将其一分为二，则其中一定有一个是有序的，另一个可能有序也可能无序。对有序部分用二分查找，无序部分再一分为二……这样循环。具体代码如下：

class Solution {
   public:    int search(vector
   
    & nums, int target) {
            int lo = 0, hi = nums.size() - 1;        while (lo <= hi) {
               int mid = lo + (hi - lo) / 2;            if (nums[mid] == target) return mid;            else if (nums[mid] < nums[hi]) {
    //右半段是有序的                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; //对右半段二分搜索                else hi = mid - 1; //右半段有序,但不在右半段的范围内,因此对左半段搜索            } else {
    //左半段有序                if (target >= nums[lo] && target < nums[mid]) hi = mid - 1; //对左半段二分搜索                else lo = mid + 1; //左半段有序,但不在左半段的范围内,因此对右半段搜索            }        }        return -1;    }};
   

提交后效率如下：

执行用时：4 ms, 在所有 C++ 提交中击败了82.70% 的用户内存消耗：11.2 MB, 在所有 C++ 提交中击败了5.21% 的用户

递归版代码如下：

class Solution {
   private:    int binarySearchInRotatedSortedArray(const vector
   
    & a, int l, int r, int t) {
           if (l > r) return -1;        int mid = l + (r - l) / 2;        if (a[mid] == t) return mid;        else if (a[mid] < a[r]) {
    //右半段有序            return (a[mid] < t && t <= a[r]) ?                binarySearchInRotatedSortedArray(a, mid + 1, r, t) :                 binarySearchInRotatedSortedArray(a, l, mid - 1, t);        } else {
    //左半段有序            return (t < a[mid] && t >= a[l]) ?                binarySearchInRotatedSortedArray(a, l, mid - 1, t) :                binarySearchInRotatedSortedArray(a, mid + 1, r, t);        }    }public:    int search(vector
    
     & nums, int target) {
            return binarySearchInRotatedSortedArray(nums, 0, nums.size() - 1, target);    }};
    
   

递归版的效率低一些：

执行用时：8 ms, 在所有 C++ 提交中击败了45.60% 的用户内存消耗：11.4 MB, 在所有 C++ 提交中击败了5.21% 的用户

进阶题目：

转载地址：https://memcpy0.blog.csdn.net/article/details/109193191 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！