搜索旋转排序数组

33.搜索旋转排序数组

题目描述

题解

为了设计一个复杂度为 \(O(logn)\) 的算法，可以采用二分的思想，但是题给数组只是一个部分有序的数组，更准确一点，应该是两个有序数组拼接而成的部分有序数组，唯一出现乱序的地方就是两个数组的拼接处。为了使用二分查找算法，我们必须确定中位点mid位于哪一个有序数组中。这里提供一个简单的思路，我们将nums[mid]与nums[0]作比较，由于数组中的元素互不相等，因此：

1.nums[mid] > nums[0]：那么左半部分[left, mid-1]有序
2.nums[mid] < nums[0]：那么右半部分[mid+1, right]有序

如果target==nums[mid]，查找成功，退出。

在上述条件1的情况下，如果：target的值介于[nums[0], nums[mid]) 之间，则往左半部分遍历，否则往右半部分遍历。

在上述条件2的情况下，如果：target的值介于(nums[mid], nums[n-1]] 之间，则往右半部分遍历，否则往左半部分遍历。
代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int n = (int)nums.size();
        if (!n) return -1;
        
        if (n == 1) return nums[0] == target ? 0 : -1;
        
        int l = 0, r = n - 1;
        while (l <= r) 
        {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            //[0, mid-1]有序
            if (nums[0] <= nums[mid]) 
            {
                if (nums[0] <= target && target < nums[mid]) 
                {
                    r = mid - 1;
                } 
                else 
                {
                    l = mid + 1;
                }
            } 
            //[mid+1, n-1]有序
            else 
            {
                if (nums[mid] < target && target <= nums[n - 1]) 
                {
                    l = mid + 1;
                } 
                else 
                {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};

该题的思想在于：每次二分时，将一个较大的部分有序的数组转化为一个较小的有序数组和一个较小的部分有序数组。