背景

二分的思想很简单，但是难在 coding 上，因为需要考虑边界条件

在 B 站上看了一个视频，二分查找为什么总是写错？动画讲解了一种比较好记忆处理边界的方式（我认为并不是在讲二分的思想，而是用一种图示的方式避免边界处理错误），所以在这里记录下

应用

引入抛出了一个问题

有这样一个有序数组 [1,2,3,5,5,5,8,9]，需要找出如下答案

找到第一个大于等于 5 的元素
找到最后一个小于 5 的元素
找到第一个大于 5 的元素
找到最后一个小于等于 5 的元素

新角度

使用二分查找符合条件的下标，下标的本质就是分界点 K，假设分界点将数组分为了红蓝两部分

一共有 N 个元素
元素的编号为 0 ~ N - 1
前 K 个元素为蓝色，后 N - K 个元素为红色

( 0 ) ( 1 ) ( 2 ) ... ( k - 1 ) ( k ) ... ( N - 2 ) (N - 1)

伪代码

# l 从 - 1 开始
l = -1
# r 从 N 开始（size）
r = N
# 循环边界为 l 一定在 r 的左边
while l + 1 < r
	# 二分中点
	m = (l + r) / 2
	# isBlue 的本质是需求中需要找出的分界点 K 的判断规则
    if isBlue(m)
    	# 指针移动
    	l = m
    else
    	r = m
# 根据需求选择使用分界点前的元素还是后面的元素
return l or r

这里需要论证几个问题：

为什么 l 要从 -1 开始，而 r 从 N 开始 想象出一个红蓝区间，如果 l 从 0 开始，那么至少代表 index = 0 的位置也是蓝色，而这是不合理的；对于 r 同理
为什么循环条件为 l + 1 < r 想象出一个红蓝区间，如果 l 和 r 有交叉，那么交叉区域既是蓝色又是红色，也是不合理的
m 的值一定是 [0,N) 吗 在整段逻辑中，l 的最小值为 -1，r 的最小值为 1（为什么 r 不会为 0，因为 0 的话，l + 1 < r 不会进入循环），那么 m 的最小值为 0 最大值同理，r 的最大值为 N，l 的最大值为 N - 2，那么 m 的最大值为 N - 1

解决上述问题

套用这个红绿区间的模板，就可以得到上面四个问题的答案

问题	蓝红划分	isBlue 条件	返回
找到第一个大于等于 5 的元素	( 1 ) ( 2 ) ( 3 ) ( 5 ) ( 5 ) ( 5 ) ( 8 ) ( 9 )	小于 5	r
找到最后一个小于 5 的元素	( 1 ) ( 2 ) ( 3 ) ( 5 ) ( 5 ) ( 5 ) ( 8 ) ( 9 )	小于 5	l
找到第一个大于 5 的元素	( 1 ) ( 2 ) ( 3 ) ( 5 ) ( 5 ) ( 5 ) ( 8 ) ( 9 )	小于等于 5	r
找到最后一个小于等于 5 的元素	( 1 ) ( 2 ) ( 3 ) ( 5 ) ( 5 ) ( 5 ) ( 8 ) ( 9 )	小于等于 5	l

找到第一个大于等于 5 的元素

public class Binary {

    public static void main(String[] args) {
        int index = findFirstGte5Index(Arrays.asList(1, 2, 3, 5, 5, 5, 8, 9));
        System.out.println(index);
    }

    public static int findFirstGte5Index(List<Integer> list) {
        int left = -1;
        int right = list.size();
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int n = list.get(mid);

            // isBlue 条件 小于 5
            if (isLt5(n)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        // 返回 r
        return right;
    }

    private static boolean isLt5(int n) {
        return n < 5;
    }
}

找到最后一个小于等于 5 的元素

public class Binary {

    public static void main(String[] args) {
        int index = findLastLte5Index(Arrays.asList(1, 2, 3, 5, 5, 5, 8, 9));
        System.out.println(index);
    }

    public static int findLastLte5Index(List<Integer> list) {
        int left = -1;
        int right = list.size();
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int n = list.get(mid);

            // isBlue 条件 小于等于 5
            if (isLte5(n)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        // 返回 l
        return left;
    }

    private static boolean isLte5(int n) {
        return n <= 5;
    }
}

参考

二分查找为什么总是写错？_哔哩哔哩_bilibili

贫瘠之地

二分查找红蓝分区思想

背景

应用

新角度

伪代码

解决上述问题

参考