【LeetCode题解】LeetCode 33. 搜索旋转排序数组

【题目链接】
33. 搜索旋转排序数组
【题目描述】

【题解】
对于一个有序数组，我们可以使用二分查找算法来查找某个元素，具体的算法模板可以参考【算法基础课-算法模板1】基础算法中二分查找一节的内容。
然而，在这道题目中，数组并不是完全有序的，而是经过旋转后，只保证了数组的某一部分是有序的。那么，是否仍然可以使用二分查找算法呢？答案是可以的。我们可以利用旋转数组的性质，通过判断数组的哪一部分是有序的，来调整查找范围，从而有效地应用二分查找算法。
通过观察常规的二分查找算法，我们可以看到 mid 将原本有序的序列划分为 [l, mid] 和 [mid+1, r] 两个部分。因此，我们可以借鉴这一思想来解决本题。在这道题中，我们可以通过判断 [l, mid] 和 [mid+1, r] 这两部分中哪一部分是有序的，然后根据这个有序部分来调整二分查找的上下边界。具体而言，若某一部分是有序的，我们就可以判断目标值 target 是否位于该有序部分内，从而决定是将查找范围缩小到该部分，还是缩小到另一部分。这种方法使得我们能够在旋转数组中有效地找到目标值。

• 如果[l, mid]是有序数组，且target的大小满足[nums[l], nums[mid])，则我们应该将搜索范围缩小至[l, mid - 1]，否则将搜索范围缩小至[mid + 1, r]。
• 如果[mid, r]是有序数组，且target的大小满足(nums[mid], nums[r]]，则我们应该将搜索范围缩小至[mid + 1, r]，否则将搜索范围缩小至[l, mid - 1]。

例如：
nums=[4,5,6,7,0,1,2]，其中l=0,r=6,mid=3，[l,mid]是有序数组，
如果target=5，在[l,mid-1]中寻找；
如果target=2，在[mid+1,r]中寻找。
nums=[6,7,0,1,2,3,4,5]，其中l=0,r=6,mid=3，[mid,r]是有序数组，
如果target=6，在[l,mid-1]中寻找；
如果target=4，在[mid+1,r]中寻找。

【AC代码】

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r) {
            int mid = l + r >> 1;
            // 如果找到了目标值，直接返回下标
            if(nums[mid] == target)
                return mid;
            // 判断哪一部分是有序的
            if(nums[l] <= nums[mid]) { // 左半部分有序
                if(nums[l] <= target && target < nums[mid]) 
                    r = mid - 1; // 目标在左半部分，缩小右边界
                else //
                    l = mid + 1; // 目标不在左半部分，缩小左边界
            } else { // 右半部分有序
                if(nums[mid] < target && target <= nums[r])
                    l = mid + 1;  // 目标在右半部分，缩小左边界
                else
                    r = mid - 1; // 目标不在右半部分，缩小右边界
            } 
        }

        return -1;
    }
};