lc/rotate_search.cpp at master · ppl5/lc · GitHub

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
int rotateSearch(vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size() - 1;

    while (l <= r) {
        int mid = ((r - l) >> 1) + l;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[l] <= nums[r]) {
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        } else {
            if (nums[l] <= target) {
                if (nums[mid] <= nums[r]) {
                    r = mid - 1;
                } else if (nums[mid] < target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            } else {
                if (nums[mid] >= nums[l]) {
                    l = mid + 1;
                } else if (nums[mid] < target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
    }

    return -1;
}