• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

LeetCode 81. 搜索旋转排序数组 II

互联网 diligentman 2周前 (04-07) 10次浏览

二分思想,后期需要系统的过一遍;

 

自己想的是按照索引取模进行标准二分的判断,但是官方思路更加简单;

步骤大致如下:

直接取mid,由于中枢节点存在,必定会存在下列两种情况:

1.mid在中枢节点左边,则l~mid区间为有序;

2.mid在中枢节点右边,则r~mid区间为有序;

之所以关注于有序区间,主要是因为能保证二分判断循环的执行;

class Solution {
public:
    bool search(vector<int> &nums, int target) {
        int n = nums.size();
            if (n == 0) {
                return false;
            }
            if (n == 1) {
                return nums[0] == target;
            }
            int l = 0, r = n - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] == target) {
                    return true;
                }
                if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                    ++l;
                    --r;
                } else if (nums[l] <= nums[mid]) {
                    if (nums[l] <= target && target < nums[mid]) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                } else {
                    if (nums[mid] < target && target <= nums[n - 1]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
            }
        return false;
    }

};

 

展开阅读全文

© 著作权归作者所有

举报

打赏

0


0 收藏

微信
QQ
微博

分享

作者的其它热门文章

LeetCode 74. 搜索二维矩阵
Linux基础 关于缓冲区和cp、who的指令实现


程序员灯塔
转载请注明原文链接:LeetCode 81. 搜索旋转排序数组 II
喜欢 (0)