二分法 | Dream sea

折半查找又称二分查找，仅适用于有序的顺序表 (可随机访问，链表不行)。

给出如下形式的代码：假设查找表为从小到大的有序表，显然一般而言当 $low>high$ 时认为查找失败。

typedef int ElemType;
typedef struct
{
    ElemType *elem;
    int tableLen;
} SSTable;

int Binary_Search(SSTable L, ElemType key)
{
    int low = 0, high = L.tableLen - 1, mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (L.elem[mid] == key)
        {
            return mid;
        }
        else if (L.elem[mid] > key) // key在左半区
        {
            high = mid - 1;
        }
        else // key在右半区
        {
            low = mid + 1;
        }
    }
    return -1;
}

折半查找判定树构成：首先我们要知道在 c 或 c++语言中， $mid = (low + high) / 2$ 其实是等同于 $mid=\lfloor \frac{low+high}{2}\rfloor$ 。
1. $mid=\lfloor \frac{low+high}{2}\rfloor$ $mi d = ⌊ \frac{l o w + hi g h}{2} ⌋$ 时：每次二分后， $high$ 到 $low$ 元素个数的奇偶性是可能发生变化的。
  1. 若 $high$ 到 $low$ 共有奇数个元素时，则 $mid$ 分隔后，左右两边元素个数相等。
  2. 若 $high$ 到 $low$ 共有偶数个元素时，则 $mid$ 分隔后，左边元素个数比右边少一个。
  3. 对于任意一个判定树结点，右子树结点数-左子树结点数= $0$ 或者 $1$ 。
2. $mid=\lceil \frac{low+high}{2}\rceil$ $mi d = ⌈ \frac{l o w + hi g h}{2} ⌉$ 时：
  1. 若 $high$ 到 $low$ 共有奇数个元素时，则 $mid$ 分隔后，左右两边元素个数相等。
  2. 若 $high$ 到 $low$ 共有偶数个元素时，则 $mid$ 分隔后，右边元素个数比左边少一个。
  3. 对于任意一个判定树结点，左子树结点数-右子树结点数= $0$ 或者 $1$ 。
3. 故而经上面分析，折半查找的判定树一定是平衡二叉树，且除最后一层可能不满以外，其它层都是满的。含有元素个数 $n$ 的树高 (不含失败结点) 为 $h=\lceil log_2 (n+1) \rceil$ ，显然 $ASL_{成功}<=h$ 且 $ASL_{失败}<=h$ ，即折半查找时间复杂度 $o(log_2n)$ 。但是请注意，这不意味着任何情况下折半查找的效率均高于顺序查找，例如查找查找表的第一个元素。
4. 显然依旧满足：若有 $n$ 个结点，则相应地有 $n+1$ 个查找失败结点 (成功结点的空链域数量)。
5. 下面我们不妨演示一下 $mid=\lfloor \frac{low+high}{2}\rfloor$ $mi d = ⌊ \frac{l o w + hi g h}{2} ⌋$ 的判定树构建过程 (下图省略失败结点部分)：
  1. 显然按照左子树比右子树少一原则， $16$ 和 $41$ 因该是右孩子。
  2. 当然我们其实要知道在折半查找的判定树中，左右子树其实就是在折半过程中划分的左右区间。当 $mid=13$ 时显然 $16$ 属于右区间内，故而在右子树中， $41$ 同理可得。
6. 不妨判断一下面的二叉树是否可能是折半查找的判定树：显然不是，不可能一会右子树比左子树多，一会儿左子树比右子树多。
提醒一点：mid=(left+right)/2存在left+right过大导致溢出的风险，推荐使用mid=left+(right-left)/2。
为了后续分块查找部分，提一嘴。实际上查找关键字并不是二分查找的全部内容，例如如何找到一个比关键字大的最小值、或者找比关键字小的最大值。实际上我们要知道一点：查找失败， $low$ 和 $high$ 会分别指向比目标值稍大和稍小的元素，如下图两种情况的演示。当然也可以直接尝试逻辑分析，当 $low=high$ 时，若 $arr[mid] \leq key$ 显然 $low$ 右移，反之 $high$ 左移，故而不难看出上述结论。不妨尝试力扣题：搜索插入位置 (由于不存在重复，若找到相等元素时返回当前位置即可)

补充：但是对于上述问题，其存在一个前提查找表中无重复元素。但是当我们允许重复时情况似乎略复杂，即允许存在重复元素，此时我们需要深入理解一下二分法的原理：为了方便叙述，这里暂时使用 $arr$ 代替 $L.elem$ ，开启上帝视角，将程序的查找结果(最终返回值)记作 $ans$ 。

前提：关于程序结束条件的讨论
1. low<high：当循环结束时low=high，此时对于双闭区间( $[low,high]$ )而言，我们已经找到一个值 $hiht=low$ ,下一步就是判断 $high=low$ 是不是我们要的 $ans$ ,不是则没结果。
2. low<=high：当循环结束时low=high+1，此时对于双闭区间( $[high,low]$ )而言，我们找到两个值high和low。这时后我们需要判断，我们 $ans$ 是其中哪一个，还是都不是。
3. 实际上low<=high就是在low<high的基础上再运行了一遍程序，这个过程其实就可以认为将low=high得到的唯一结果进行验算，判断是否为我们要的 $ans$ 。
现在，我们不妨提出以下两个问题：
1. $A$ ：在一个存在重复元素的查找表中，我们需要找到比 $key$ 大的最小值。
2. $B$ ：在一个存在重复元素的查找表中，我们需要找到比 $key$ 小的最大值。
显然无论是哪个问题，有一点我们需要肯定。当low=high时，我们就要终止程序,即终止条件仍为low<high(这一点通过后面讨论很容易理解)。而一般二分法之所以在low=high后还执行一遍程序，是为了判断最终找到位置的关键字是不是key。参照这个形式，其实可以写出另一种二分法代码如下，这个我们后面再说。

对于问题 $A$ ,当我们发现 $L.elem[mid] \leq key$ 时，我们该怎么做？显然我们需要找比 $key$ 大的，我们可以直接 $low=mid+1$ 。当我们发现 $L.elem[mid] \gt key$ 时，我们该怎么做？显然我们需要保留 $mid$ ，因为 $mid$ 可能就是我们需要的结果，即 $high=mid$ 。给出下列代码:

int binary_search(SSTable ST, ElemType key)
{
    int low = 0, high = ST.tableLen - 1, mid;
    while (low < high)
    {
        mid = (low + high) / 2;
        if (ST.elem[mid] <= key)
            low = mid + 1;
        else
            high = mid;
    }
    return ST.elem[low] > key ? low : -1;
}

当然对于上述代码最后返回值可能存在一些小的疑问,为啥不直接返回low?其实可能high一直没动，low一路狂奔追上high，也就是说整个数组可能不存在比key大的数。

那么若将low<high的条件换为low>=high呢？给出如下代码：显然当high=low时，我们找到可能结果; 此时若low是所求ans则low不变，否则low加一则没找则返回low即可(当然也可以推测low+1=high时的情形)。

int Search_Bin(SSTable ST, ElemType key)
{
    int low = 0, high = ST.tableLen - 1, mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (ST.elem[mid] <= key)
            low = mid + 1;
        else
            high = mid;
    }
    return low; // high+1也是可以的
}

同样的，对于问题 $B$ , 当我们发现 $L.elem[mid] \geq key$ 时，我们该怎么做？显然我们需要找比 $key$ 小的，我们可以直接 $high=mid-1$ 。当我们发现 $L.elem[mid] \lt key$ 时，我们该怎么做？显然我们需要保留 $mid$ ，因为 $mid$ 可能就是我们需要的结果，即 $low=mid$ 。给出下列代码:

int Search_Bin(SSTable ST, ElemType key)
{
    int low = 0, high = ST.tableLen - 1, mid;
    while (low < high)
    {
        mid = (low + high) / 2;
        if (ST.elem[mid] < key)
            low = mid;
        else
            high = mid - 1;
    }
    return ST.elem[high] < key ? high : -1;
}

同理可以写出 $B$ 问题的另一种代码：

int Search_Bin(SSTable ST, ElemType key)
{
    int low = 0, high = ST.tableLen - 1, mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (ST.elem[mid] < key)
            low = mid;
        else
            high = mid - 1;
    }
    return high; // low-1也是可以的
}

实际上，我们给出折半查找的另一种解释，即排除法解释，上述代码就会变得和蔼可亲。

先以基本的折半查找为例，当我们发现 $arr[mid]>key$ ，显然我们的 $ans \lt mid$ 于是乎排除右区间转向左区间，其代码语言就是 $high=mid-1$ 。而当我们发现 $arr[mid]<key$ ，显然我们的 $ans \gt mid$ 于是乎排除左区间转向右区间，其代码语言就是 $low=mid+1$ 。
在次回到 $A$ 问题中，我们的 $arr[ans]>key$ ，当 $arr[mid]=key$ , 显然我们显然需要排除左区间，同理当 $arr[mid]<key$ ，我们也需要丢弃左区间，转换为代码语言就是 $low=high+1$ 。那么当 $arr[mid]<key$ 时，此时 $mid$ 可能就是 $ans$ ，需要保留 $high=mid$ 。对于 $B$ 问题同理分析即可。

排除法的精髓在于，不断排除不可能存在结果的区间直至区间长度为1，那么我们的结果要不就是这玩意，要不就没结果。于是我们根据上述知识得到新的二分代码：当然不难看出，这种形式的效率较低，每次都需要遍历整个表才能得出最后结果，哪怕是中间某个过程中 $arr[mid]=key$ 。

int Binary_Search(SSTable L, ElemType key)
{
    int low = 0, high = L.tableLen - 1, mid;
    while (low < high)
    {
        mid = (low + high) / 2;
        if (L.elem[mid] > key)
        {
            high = mid - 1;
        }
        else
        {
            low = mid;
        }
    }
    return L.elem[low] == key ? low : low - 1;
}

int Binary_Search(SSTable L, ElemType key)
{
    int low = 0, high = L.tableLen - 1, mid;
    while (low < high)
    {
        mid = (low + high) / 2;
        if (L.elem[mid] < key)
        {
            low = mid + 1;

        }
        else
        {
            high = mid;
        }
    }
    return L.elem[low] == key ? low : low - 1;
}

此外对于 $A$ 和 $B$ 问题，我们提出另一种略难理解的方式，区间开闭。

给出示意图：其中数组长度为 $n$

对于 $A$ 问题，我们需要找比 $key$ 大的关键字，即 $ans$ 。那么 $ans$ 在数组中的位置在哪儿？显然存在多种表示：

$0 \leq ans \leq n-1$ ，我们称这种为双闭区间，就是我们上面代码所使用的区间法。

$0 \leq ans \lt n$ ，我们称这种为左闭右开区间，这种形式可以解决 $A$ 问题：我们在理论上n补上，这样就没有必要在high=low后验证一次，也不能验证，验证就可能导致数组越界。

int binary_search(SSTable ST, ElemType key)
{
    int low = 0, high = ST.tableLen, mid;
    while (low < high)
    {
        mid = (low + high) / 2;
        if (ST.elem[mid] <= key)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

$-1 \lt ans \leq n-1$ ，我们称这种为左开右闭区间，这种形式可以解决 $B$ 问题：原理同上。

int Search_Bin(SSTable ST, ElemType key)
{
    int low = -1, high = ST.tableLen - 1, mid;
    while (low < high)
    {
        mid = (low + high) / 2;
        if (ST.elem[mid] < key)
            low = mid;
        else
            high = mid - 1;
    }
    return high;
}

指鹿为马：实际上，我们前面在二分法(不含有重复元素)中提过：查找失败， $low$ 和 $high$ 会分别指向比目标值稍大和稍小的元素。那对于 $A$ 问题，我们倘若将 $=key$ 执行的操作归类到 $<key$ 的操作(将所有 $=key$ 的视作 $<key$ )，那么最终就演变成了最开始不含重复元素且必然查找失败的情景。那对于 $B$ 问题同理(将所有 $=key$ 的视作 $>key$ )

对于 $A$ 问题：

int Search_Bin(SSTable ST, ElemType key)
{
    int low = 0, high = ST.tableLen, mid; // 左闭右开
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (ST.elem[mid] <= key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low;
}

对于 $B$ 问题：

int Search_Bin(SSTable ST, ElemType key)
{
    int low = -1, high = ST.tableLen-1, mid; // 左开右闭
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (ST.elem[mid] >= key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return high;
}

最终给出一个图和一句话：二分法的关键还是讨论low=high以及其前、后一步的执行情况。