33.Search in Rotated Sorted Array

Tags: Medium Array

Link: https://leetcode.com/problems/search-in-rotated-sorted-array/

---

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

---

Answer:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return -1;
        int left = 0, right = n - 1;

        while (left <= right) {
            int middle = left + ((right - left) >> 1);
            if (nums[middle] == target) return middle;
            if (nums[middle] >= nums[left]) { //[left, middle] 升序排列
                if (nums[middle] > target &&  target >= nums[left]) right = middle - 1;
                else left = middle + 1;
            }
            else{ //[middle, right]为升序排列
                if (nums[middle] < target && target <= nums[right]) left = middle + 1;
                else right = middle - 1;
            }
        }

        return -1;
    }
};

对于二分查找这种问题，比较容易出错的地方在于何时左右边界的选取和循环的退出条件的设定。

可以总结这样的规律，比如写查找插入位置的题目，一个判断条件是<，另一个是>=，则退出一般写为left < right。如果分开写成middle, left,right，并且每次左右边界都会变化，则退出条件一般写成left <= right。这个只是写习惯了就会发现的方法，但是不能只会套模板，因为每次写完一定要检查。

检查的办法就是取特殊情形考虑：

• 数组为空是否考虑到了
• 数组只有一个元素是否考虑到了
• 数组两个元素，（本题考虑交换一下顺序进行二次检验）

上面的写法是首先得到中点的下标，然后比较中点和左端下标对应的数值，如果大于左端，则说明左端是有序的，否则就是右端有序的。但是这里考虑特殊情形是中点和左端点重合的情形，为什么会出现这种情形？因为是我们取中点的表达式造成的int middle = left + ((right - left) >> 1)，所以当数组只有两个元素，中点会定位到左端点。考虑到这里自然就知道循环终止条件不可以写成left < right。

所以如果换成与右端判断，则写成下面这种：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return -1;
        int left = 0, right = n - 1;

        while (left <= right) {
            int middle = left + ((right - left) >> 1);
            if (nums[middle] == target) return middle;
            if (nums[middle] < nums[right]) { //[left, middle] 升序排列
                if (nums[middle] < target && target <= nums[right]) left = middle + 1;
                else right = middle - 1;
            }
            else{ //[middle, right]为升序排列
                if (nums[middle] > target &&  target >= nums[left]) right = middle - 1;
                else left = middle + 1;
            }
        }

        return -1;
    }
};

会发现其实就是调换了一下判断语句的内容，如果想写成nums[middle] <= nums[right]这种情况，也就是最后两个点的时候，要让中点取在右端，需要改动的是中点的取法int middle = right - ((right - left) >> 1)，这样每次判断的条件也会略有改动，可自行测试。