LeetCode

LeetCode-33 搜索旋转排序数组

nkul · 10月1日 · 2020年 · 24次已读

如上图,普通的有序数组在坐标轴如左图所示,旋转数组如右图所示!

现用二分法找到旋转点!

旋转数组分两段,第一段有特征 nums[i] > nums[0],第二段有特征nums[i] < nums[0]

int l = 0, r = nums.size() - 1;
//第一个二分找到旋转点!
while( l < r){
    int mid = (l + r + 1) >> 1;
    if(nums[mid] >= nums[0]) l = mid ;
    else{
        r = mid - 1;
    }
}

此时 l = r = 旋转点!

将target和nums[0]比较,确定target在哪一段

if(target >= nums[0])
    l = 0;
else
    l = r + 1, r = nums.size() - 1;

后续就是正常有序数组的二分查找了!

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

if(nums[r] == target) return r;
return -1;

最终代码如下:

class Solution {
public:
    int search(vector& nums, int target) {
        if(nums.empty()) return -1 ;
        int l = 0, r = nums.size() - 1;
        //第一个二分找到旋转点!
        while( l < r){
            int mid = (l + r + 1) >> 1;
            if(nums[mid] >= nums[0]) l = mid ;
            else{
                r = mid - 1;
            }
        }
        //此时l = r 等于旋转点
        if(target >= nums[0]) l = 0;
        else l = r + 1, r = nums.size() - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(nums[mid] >= target) r= mid;
            else l = mid + 1;
        }
        if(nums[r] == target) return r;
        return -1;
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!