Cinte's Leetcode Record
0%

33. Search in Rotated Sorted Array

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

33. Search in Rotated Sorted Array

参考面试题 10.03. 搜索旋转数组

区别在于这题的数字不重复

First Time
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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int sz = nums.size();
        auto bias = binarySearch(nums, 0, sz - 1);
        int lo = 0, hi = sz;
        int mid;
        while(lo < hi)
        {
            mid = (lo + hi) / 2;
            if(nums[(mid + bias) % sz] < target)
            {
                lo = mid + 1;
            }else
            {
                hi = mid;
            }
        }
        return (nums[(hi + bias) % sz] == target) ? (hi + bias) % sz : -1;

    }
private:
    int binarySearch(vector<int>& nums, size_t lo, size_t hi)
    {
        int mid;
        while (lo < hi)
        {
            mid = (lo + hi) / 2;
            if (nums[mid] > nums[hi])
            {
                lo = mid + 1;
            }
            else
            {
                hi = mid;
            }
        }
        return hi;
    }
};

O(logN)

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        int sz = nums.size();
        while(lo < hi)
        {
            int mid = (lo + hi) / 2;
            if(nums[mid] < nums[hi])
                hi = mid;
            else
                lo = mid + 1;
        }
        int bias = hi;
        lo = 0, hi = nums.size();
        while(lo < hi)
        {
            int mid = (lo + hi) / 2;
            if(nums[(mid + bias) % sz] > target)
                hi = mid;
            else if(nums[(mid + bias) % sz] == target)
                return (mid + bias) % sz;
            else
                lo = mid + 1;
        }
        return -1;
    }
};
review(20211030)
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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while(lo < hi)
        {
            int mid = lo + (hi - lo) / 2;
            if(nums[mid] >= target)
            {
                if(target < nums[lo] && nums[mid] >= nums[lo])
                    lo = mid + 1;
                else
                    hi = mid;
            }
            else
            {
                if(target >= nums[lo] && nums[mid] < nums[lo])
                    hi = mid;
                else
                    lo = mid + 1;
            }
        }
        return nums[hi] == target ? hi : -1;
    }
};