33.搜索旋转排序数组

😂二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int div = 0;
        int M = nums.size();
        nums.push_back(1000);
        for(;div < M; ++div) {
            if(nums[div] > nums[div + 1]) {
                break;
            }
        }
        int a = srch(nums, target, 0, div);
        if(a != -1)
            return a;
        if(div != M) {
            return srch(nums, target, div + 1, M - 1);
        }
        return -1;
    }
    int srch(vector<int>& nums, int target, int be, int ed) {
        int lo = be,
        hi = ed, mi;
        while(lo < hi) {
            mi = lo + (hi - lo) / 2;
            if(nums[mi] < target) {
                lo = mi + 1;
            } else {
                hi = mi;
            }
        }
        if(nums[lo] == target)
            return lo;
        return -1;
    }
};

Accepted

196/196 cases passed (4 ms)

Your runtime beats 89.74 % of cpp submissions

Your memory usage beats 5.18 % of cpp submissions (9.1 MB)