LeetCode 33.搜索旋转排序数组

主页有其他数据结构内容（持续更新中）

难度：Medium

代码：

使用蓝红二分法模板

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = -1;
        int right = n;
        //  第一次二分：找出旋转点
        while(left + 1 < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= nums[0]) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        //  判断target在旋转点左边还是右边
        if(target >= nums[0]) {
            left = -1;
        }
        else {
            right = n;
        }
        //  第二次二分：判断是否存在target并找出下标
        while(left + 1 < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] <= target) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        if(left <= right && nums[left] == target) {
            return left;
        }
        else {
            return -1;
        }
    }
};
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
40
41