Fork me on GitHub

面试题10.03.搜索旋转数组

发表于 | 分类于 ， | 次阅读
字数统计: 439 | 阅读时长 ≈ 1

基本思路

这道题是数组旋转，而不会有局部旋转，所以旋转后的数组一定会形成两段，且前一段中每个元素的值一定大于等于后一段每个元素的值，且两段都是各自升序排列。如果是一段的话，那就是原数组了。

既然是两段，那么这两段一定会有长度上的区别，我们设$left$为数组左端，$right$为数组右端。如图所示：

1

1

  • 如果$mid$大于$left$，那么第一段长度大于第二段，从$left$到$mid$是一段升序的排列，我们可以通过$target$的值和$v[left]和v[mid]$比较来得出下一步的范围。
  • 如果$mid$小于$left$，那么第一段长度小于第二顿，从$mid$到$right$是一段降序的排列，我们可以通过$target$的值和$v[left]和v[mid]$比较来得出下一步的范围。

当$v[mid] == v[left]$时是特殊情况

如图所示：

1

当$v[mid] == v[left]$时，如果$target != v[mid]$，那么下一步的位置没法直接判断出来，需要$left++$ 来逐一缩小范围。

代码

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
class Solution {
public:
    int search(vector<int>& arr, int target) {
        int left = 0 , right = arr.size() - 1;
        while(left < right){
            if(arr[left] == target) return left;
            int mid = (left + right) / 2;
            if(arr[left] < arr[mid]){
                if(arr[left] <= target && target <= arr[mid]){
                    right = mid;  //target == arr[mid]也是向左缩小范围，因为题目要求值相同的输出最小位置
                }
                else left = mid + 1;
            }
            else if(arr[left] > arr[mid]){
                if(arr[left] <= target || arr[mid] >= target){
                    right = mid;
                }
                else left = mid;
            }
            else if(arr[left] == arr[mid]){  //特殊情况
                if(arr[left] == target){
                    right = left;
                }
                else left++;
            }
        }
        return (arr[left] == target) ? left : -1;
    }
};