我写了首诗，把二分搜索算法变成了默写题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：我写了首诗，把二分搜索算法变成了默写题

评论礼仪 见这里，违者直接拉黑。

[Calmlzw]

自己验证了下34题，不能直接套用，有些case没有过，期望修复

[labuladong]

@Calmlzw @theSavageseens 说具体一些？我试了下可以通过的。

[ThomasQY]

试了34题，python是没问题的（下面答案里有个大哥建议直接用.index()笑死）

[yuchengkang]

试了34题，Java是没问题的

[wyzjb123]

C++也通过了，上面出错的同学，应该是没有注意循环后的细节吧？（比如我就是左边界忘记检查等于数组大小的时候了😥）

[RuiMM]

秒

[feymanpaper]

妙呀

[alannesta]

双闭区间是精髓

[bbfxier]

寻找左侧边界的⼆分搜索中
// target 比所有数都大
if (left == nums.length) return -1;
不是应该返回nums.length嘛？

[PsycoTodd]

能否也讲解一下，如果数组里面不含有查找元素，那么如果找最左和最右，返回的值是否可以保证是数组里第一个比target大或者小的数？

[tn233]

C，34题没问题（双闭区间）

[admn410]

自己验证了下34题，不能直接套用，有些case没有过，期望修复

不好意思，又重新验证了下，是正确的，之前应该是自己哪里弄错了，麻烦把这个issue删了吧，总是有推送邮件

[yfmei]

一开始就判断 target 是否存在，最后就不用考虑越界的事了。

if (target < nums[left] || target > nums[right]) {
    return -1;
}

[mrpersimmon]

当数组为空，这种写法就会报错

[JiachengZhao98]

请问大家我这样判断空数组为什么了leetcode不给过啊
if(nums.size() == 0)
{
return {-1, -1};
}
leetcode一直显示runtime error

[shallowshadowshade]

用.empty()

[z-ak-z]

@JiachengZhao98
数组求长度，用这个：nums.length

[gaokai320]

寻找左侧边界时，通过不断左移right，逼近左侧边界，left始终锚定左侧边界；也就是：

if (left == nums.length || nums[left] != target)

寻找右侧边界时，通过不断右移left，逼近右侧边界，right始终锚定右侧边界；也就是：

if (right < 0 || nums[right] != target)

[CarlLy7]

打卡喽，跟着东哥学算法，越学越上瘾，希望东哥能继续更新好作品！！感谢东哥

[iiimapidan]

寻找一个数（基本的二分搜索）小结中：
while(left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空

寻找左侧边界的二分搜索小结中：
因为 right = nums.length 而不是 nums.length - 1。因此每次循环的「搜索区间」是 [left, right) 左闭右开。
while(left < right) 终止的条件是 left == right，此时搜索区间 [left, left) 为空，所以可以正确终止。

都是使用while(left < right)判断，达到终止条件后，为什么第1个搜索区间是[right, right]，区间非空，而第2个搜索区间是 [left, left) 区间为空。

[Loonngg]

实际写的时候要注意越界的判别

if (left - 1 < 0) return -1;

后面加个else就行

[pzheng460]

我觉得比如right=mid+1的核心原因不是因为mid 已经搜索过，应该从搜索区间中去除，这种说法太模糊了。事实上，如果mid不+1的话，因为整除的向下取整，会导致结果在一个值原地踏步，得不到正确的结果

[labuladong]

有意思的视角，这个视角是否可以解释左闭右开区间 mid 不加一的情况呢？

[zhongyzyt]

对于第四条的逻辑统一的写法里，统一的left_bound的最后的判断条件有问题，left<.这个判断条件是无意义的，因为不会出现left<0的情况，在这个函数里，left初始化为0，后续没有对left进行左移操作，同理，right_bound中也不需要判断right>=nums.length，因为right没有进行过右移操作

[labuladong]

之前有说这个问题，主要是为了降低记忆成本，多几个判断也无妨：

[RayL01]

还是不懂为什么要left - 1，

[RayL01]

自己画了个图就懂了hhh

[zhangmuwuge]

仔细推导了一下。。。下面是闭区间的分析
寻找左边界（>=target的index最小者）的时候 因为 当nums[mid] >= target时, right = mid-1;当nums[mid]<target的时候,left = mid+1,最钟退出循环的时候 [left,right],此时不满足 left <= right ,由上面这句话可知, right+1 >= target恒成立,因为right肯定是由 其中某一轮的mid^-1得出来的,在这某一轮中的 nums[mid^] >= target是恒成立的,也就是nums[mid+1]>=target恒成立.,所以寻找左边界的时候最终结果写成 nums[right+1]可能更严谨一点(可解释的,当然left = right+1也是成立的,所以最后的结果用left也是可以的);

寻找右边界(<=target的index最大者)的时候,因为nums[mid]<=target时,left = mid +1;当nums[mid]>target的时候right = mid-1;
最终退出循环的时候[left,right],此时 left = right +1; 当退出循环的时候,nums[left-1]<=target,nums[right+1]>target==>nums[left]>target是恒成立的(证明过程略过,很明显啊),这个时候想要找到右边界 也就是 =target的最后一个值,这个时候不能取left,因为 nums[left]>target,所以只能往前找一个---left-1 （为啥不能往left右边找，因为left右边的值一定是 >target的!!!!!）也就是 right，感觉结果写成left-1更可解释一点。。。

[myalice-forever]

感谢总结，终于理解了一点二分搜索最后返回值为什么会是这样了

[hilenti]

怎么感觉有些地方return left-1和right需不需要减一写错了，前面例子的代码和后面例子的代码不同。（可以这样说模板给的太多不易观看）

[wild-chigga]

记得以前大神的写法是：while left+1 < right，为什么改成了while left <= right呢

[cold-runner]

东哥，在left <= right的统一写法中，求左边界最后的补丁部分if(left < 0 || left >= nums.size())这里，left指针原则上来说只可能向右移动，所以left < 0的判断条件是否是多余的？

同理，在在left <= right的统一写法中，求右边界最后的补丁部分if(right < 0 || right >= nums.size())这里，right指针原则上来说只可能向左移动，所以right >= nums.size()的判断条件是否也是多余的？

[cold-runner]

不好意思东哥，我漏看了你写的Tips

[syz6]

总结二分搜索任意位置（binarySearchAny），二分搜索左边界（binarySearchLeft） 和 二分搜索右边界（binarySearchRight） 3 个算法的通用模板。下文 nums[a..b) 表示法表示 nums 的子区间，"[", "]" 表示闭区间，"(", ")" 表示开区间。

1. 3 个算法仅第 11 行不同
2. 算法签名中，nums 按从小到大排序，搜索范围为 nums[start..end]，target 是搜索目标。
3. 用 i 表示返回值，若 i >= start，则 i 在 3 个算法中分别表示 target 的任意位置，左边界 和 右边界。否则表示找不到 target，可通过 i 计算 target 的插入位置，用 k 表示 target 的插入位置，则 i = -(k - start) - 1 + start，k = -(i - start) - 1 + start。k 满足条件：nums[start..k)< target && nums[k..end] > target。
4. 3 个算法都有循环常态（循环不变式），循环常态在循环体开始前，每次循环开始时，循环体结束后都成立。
   a. binarySearchAny 的循环常态：nums[start..left) < target, nums(right..end] > target。
   b. binarySearchLeft 的循环常态：nums[start..left) < target, nums(right..end] >= target。
   c. binarySearchRight 的循环常态：nums[start..left) <= target, nums(right..end] > target。

int binarySearchAny(int[] nums, int start, int end, int target) {
        int targetIndex = -1;
        int left = start, right = end;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midNum = nums[mid];
            if (target < midNum) right = mid - 1;
            else if (target > midNum) left = mid + 1;
            else {
                targetIndex = mid;
                break;
            }
        }

        return targetIndex != -1 ? targetIndex : -(left - start) - 1 + start;
    }

int binarySearchLeft(int[] nums, int start, int end, int target) {
        int targetIndex = -1;
        int left = start, right = end;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midNum = nums[mid];
            if (target < midNum) right = mid - 1;
            else if (target > midNum) left = mid + 1;
            else {
                targetIndex = mid;
                right = mid - 1;
            }
        }

        return targetIndex != -1 ? targetIndex : -(left - start) - 1 + start;
    }

int binarySearchRight(int[] nums, int start, int end, int target) {
        int targetIndex = -1;
        int left = start, right = end;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midNum = nums[mid];
            if (target < midNum) right = mid - 1;
            else if (target > midNum) left = mid + 1;
            else {
                targetIndex = mid;
                left = mid + 1;
            }
        }

        return targetIndex != -1 ? targetIndex : -(left - start) - 1 + start;
    }

[BobbyWucj]

leetcode 34题，CPP最优雅解法

class Solution {
    int lowerBound(const vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target)
                right = mid-1;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid-1;
        }
        if (left == nums.size() || nums[left] != target)
            return -1;
        return left;
    }

    int upperBound(const vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target)
                left = mid + 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        return {lowerBound(nums, target), upperBound(nums, target)};
    }
};

[Dark2Flame]

我的理解

搜索区间的开闭问题

right == nums.size())-1就表明这个二分搜索是两端都闭的搜索区间 ==>循环条件就是(left <= right)即退出时的状态是[right+1,right]

left和right的移动问题

首先明确一点mid是被访问过的下标所以不在下次的搜索范围之内 ==> 当搜索区间向右收缩时为[mid +1, right]；当搜索区间向左收缩时为[left, mid-1]

[qzlu-cyber]

是我笑点太低吗？开头的笑话我笑了很久😂