Cinte's Leetcode Record
0%

面试题 10.03. 搜索旋转数组

Posted on Edited on In Disqus:
Symbols count in article: 1.9k Reading time ≈ 2 mins.

面试题 10.03. 搜索旋转数组

边界条件真复杂。结合剑指 Offer 11. 旋转数组的最小数字 | Cinte's Leetcode Record思考

继续结合套路【旋转数组】从易到难，各个击破！ - 搜索旋转数组 - 力扣（LeetCode） (leetcode-cn.com)

对于一个旋转数组，分为2种，一种是出于旋转节点右边，一种是处于旋转节点左边。

当arr[lo] == arr[target]时，直接返回

当arr[mid] < arr.back()时，处于旋转节点右边

  1. arr[mid] > target : 此时target必定处于旋转节点右边一部分，那么hi = mid - 1
  2. arr[mid] < target : 此时target有两种情况
    1. target >= arr[0] : 表示了target处于0 ~ mid，则hi = mid - 1
    2. target < arr[0] : 表示了target处于mid ~，则lo = mid + 1

当arr[mid] > arr.back()时，处于旋转节点左边

  1. arr[mid] < target : 此时target必定位于旋转节点左边，是lo = mid + 1
  2. arr[mid] > target : 此时target有两种情况
    1. target >= arr[0] : 表示了target处于0 ~ mid，则hi = mid - 1
    2. target < arr[0] : 表示了target处于mid ~，则lo = mid + 1

重点

arr[mid] == target时，hi = mid，使其向左缩

重点2

当arr[mid] == arr.back()时，存在2种不确定的可能，对于这种情况需要单独处理，做法就是收缩区间。

那收缩区间是收缩lo还是hi呢，这里选择移动lo，因为所求的是最左的边界值，如果在前面没有返回的话，说明arr[lo]必定小于target，所以++lo后是安全的。

由此便可以进行二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int search(vector<int>& arr, int target) {
        int lo = 0, hi = arr.size() - 1;
        while(lo <= hi)
        {
            if(arr[lo] == target)
                return lo;
            int mid = lo + (hi - lo) / 2;
            if(arr[mid] == target)
                hi = mid;
            else if(arr[mid] < arr.back())
            {
                if(arr[mid] > target)
                    hi = mid - 1;
                else
                {
                    if (target >= arr[0])
                        hi = mid - 1;
                    else
                        lo = mid + 1;
                }
            }else if(arr[mid] > arr.back())
            {
                if(arr[mid] < target)
                    lo = mid + 1;
                else
                {
                    if(target >= arr[0])
                        hi = mid - 1;
                    else
                        lo = mid + 1;
                }
            }else
                ++lo;
        }
        return -1;
    }
};

review

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int search(vector<int>& arr, int target) {
        size_t lo{0}, hi{arr.size()};
        while(lo < hi) {
            auto mid{lo + (hi - lo) / 2};
            if(arr[lo] == target)
                return lo;
            if(arr[mid] > arr.back()) {
                if(arr[mid] < target)
                    lo = mid + 1;
                else {
                    if(target > arr.back())
                        hi = mid;
                    else
                        lo = mid + 1;
                }
            }else if(arr[mid] < arr.back()){
                if(arr[mid] >= target)
                    hi = mid;
                else {
                    if(target > arr.back())
                        hi = mid;
                    else
                        lo = mid + 1;
                }
            }else
                ++lo;
        }
        return (hi == arr.size() || arr[hi] != target) ? -1 : hi;
    }
};