二分查找 —— 红蓝染色法

codePJCP22024年12月2日大约 3 分钟算法数组二分查找红蓝染色法

原理

待查找区间：在这里特指未染色的部分！

以左闭右闭区间为例，对于 非递减 数组来说(其余有序数组同理)，根据一次二分我们可以确定 $[l e f t, M]$ 区间内的大小情况：

若 $n u m s [M] > t a r g e t$ , 则说明待查找的内容 (如果存在的话) 应该存在于 $[l e f t, M]$ 这一区间内，此时应该往 $M$ 左侧查找
- 此时把 $M$ 及其右侧染上蓝色 , 表示该区间内的元素满足 $> t a r g e t$
- 更新 $r i g h t = M - 1$
- 因此 $r i g h t + 1$ 一定为蓝色
若 $n u m s [M] \leq t a r g e t$ , 则说明待查找内容位于 $[M, r i g h t]$ 这一区间内，因此需要往 $M$ 右侧查找。
- 此时把 $M$ 及其左侧染上红色 , 表示该区间内的元素满足 $\leq t a r g e t$
- 更新 $l e f t = M + 1$
- 因此 $l e f t - 1$ 一定为红色
我们 不查找已染色的区域！
当待查找区间不合法的时候，结束查找
$L = R + 1$ 就是待查找元素位置

注意，一次二分只能够染一次色！因为你只能通过当前 $n u m s [M]$ 的情况确定一侧区间与 $t a r g e t$ 的大小关系。

如果换成查找左闭右开区间，那么根据上面的原理，我们也可以进行分析：

初始化区间为 $[l e f t, r i g h t)$ , 其中 $l e f t = 0, r i g h t = n u m s . l e n g t h$
进行二分： $m i d = l e f t + (r i g h t - l e f t) / 2$
判断 $n u m s [m i d]$ 与 $t a r g e t$ 的大小关系：
1. $n u m s [m i d] < t a r g e t$
  1. 说明 $m i d$ 及其左侧的元素都 $< t a r g e t$
  2. 我们把 $m i d$ 及其左侧染成红色
  3. 未染色的区间端点为 $m i d + 1$ , 更新 $l e f t = m i d + 1$
2. $n u m s [m i d] \geq t a r g e t$
  1. 说明 $m i d$ 及其右侧的元素都 $> t a r g e t$
  2. 把 $m i d$ 及其右侧染成蓝色
  3. 未染色的区间端点为 $m i d - 1$ , 但由于是 左闭右开 区间，因此我们更新 $r i g h t = m i d$ 以正好包裹未染色区间
当待查找区间不合法的时候 $l e f t = r i g h t$ ，结束查找
$L = R$ 就是待查找元素位置

思考

如果数组中存在多个 $= t a r g e t$ 的元素，那么上面介绍的方法会得到哪一个元素的下标？最左侧

这种性质与什么有关？

$O (l o g N)$ , 因为我们每次二分查找都去掉了当前待查找区间中的一半元素。

$O (1)$ , 仅使用到了若干变量

对于非递减数组，正常使用上述方法 (且能找得到的情况下) 的话，得到的会是 最左侧 元素的下标，即 $\geq t a r g e t$ 的第一个下标。

如果我们要找 $> t a r g e t$ , $< t a r g e t$ , $\leq t a r g e t$ 的元素下标的话，也可以通过这个方法来解决。

$i d x (< t a r g e t) \Leftrightarrow i d x (\geq t a r g e t) - 1$
$i d x (> t a r g e t) \Leftrightarrow i d x (\geq (t a r g e t + 1))$ (仅限整数数组可用)
$i d x (\leq t a r g e t) \Leftrightarrow i d x (> t a r g e t) - 1$