关于维基百科中含ceil的二分查找变体实现的技术疑问

这个变体里的ceil((L+R)/2)和L := m是一套避免死循环、同时不遗漏目标位置的配对设计，和标准二分查找的逻辑是互补的，具体关联可以从以下几点理解：

1. 中间索引的偏向性决定了范围收缩的方式 #

• 标准二分查找用整数除法（等价于floor((L+R)/2)）计算中间索引m，这个m会偏向左边界（比如L=0、R=1时，m=0）。此时如果目标值大于A[m]，说明目标一定在m的右侧，所以可以直接把L设为m+1，既跳过了不可能的左半部分，也保证每次循环的搜索范围严格缩小，不会死循环。
• 这个变体用ceil((L+R)/2)计算m，m会偏向右边界（比如L=0、R=1时，m=1）。此时如果A[m]<=目标值T，说明m本身就可能是目标位置，不能直接跳过（如果设L=m+1会漏掉这个位置），所以必须把L设为m，既保留了可能的目标点，又能保证范围收缩：因为m是右偏的，新的范围[m, R]的长度一定小于原范围[L, R]，不会出现循环无法终止的情况。

2. 反例验证：配对错误会导致问题 #

• 如果变体中用了ceil但把L设为m+1：比如数组[1,3,5]找T=3，第一次L=0、R=2，m=ceil((0+2)/2)=1，A[1]=3<=3，若L=m+1=2，此时L>R，循环结束后检查A[2]=5≠3，会返回错误结果。
• 如果变体中用了floor但把L设为m：比如L=0、R=1，m=0，若A[0]<=T，L保持0，循环条件L!=R永远成立，会陷入死循环。

3. 核心逻辑：平衡“不遗漏”和“能收敛” #

不管是标准实现还是这个变体，核心都是在缩小搜索范围时，同时满足两个要求：

• 不能漏掉可能的目标位置；
• 每次循环后范围必须严格缩小，避免死循环。
  ceil和L=m的配对，就是针对右偏中间点的场景，完美满足这两个要求的设计。

内容的提问来源于stack exchange，提问作者sukesh reddy