33. Search in Rotated Sorted Array 在旋转有序数组中搜索

[GH1995]

33. Search in Rotated Sorted Array

Difficulty: Medium

Suppose an array sorted in ascending order 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]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

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

Example 2:

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

Solution

Language: C++

// experiment
// 准确的控制边界
// 双端都取实边界
// low = mid + 1
// high = mid - 1;
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;

        /**
         * 不断变换 first 和 last 
         * 寻找 target
         */
        int first = 0;
        int last = nums.size() - 1;

        while (first <= last) {
            int mid = (last + first)  / 2;
            if (nums[mid] == target) return mid;

            /**
             * 通过 nums[first] 和 nums[mid] 之间的比较
             * 逼出哪段数据是排好序的
             */

            if (nums[first] <= nums[mid]) {
                // 4 5 6 7 1 2 3
                // |   |   |
                // f   m   l
                // 排序好的必然在 first 和 mid 中间

                if (nums[first] <= target && target <= nums[mid]) 
                    last = mid - 1;
                else 
                    first = mid + 1;
            } else {
                // if (nums[first] > nums[mid]) 
                //  6 7 1 2 3 4
                //  |   |   |
                //  f   m   last
                // 可以排序的必然在 mid 和 last 中间

                if (nums[mid] <= target && target <= nums[last])
                    // last - 1 所以用 = 号
                    first = mid + 1;
                else
                    last = mid - 1;
            }
        }

        return -1;
    }
};

[GH1995]

通过 nums[first] 和 nums[mid] 之间的比较，逼出哪段数据是排好序的

1. nums[first] <= nums[mid]，梯形在前，三角形在后，梯形较长，排序好的必然在 first 和 mid 中间
   • target在nums[first] <= nums[mid]中间，缩小搜索范围last = mid - 1;
   • target不在于此，first = mid + 1
2. nums[first] > nums[mid]，梯形在前，三角形在后，梯形较短，排好序的必然在mid和last中间

二分搜索法的关键在于获得了中间数后，判断下面要搜索左半段还是右半段，我们观察上面红色的数字都是升序的，由此我们可以观察出规律，如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的，我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪半边了