这种基于跳跃步长的二分查找算法是如何运行的？

前置前提 #

这个实现有两个默认前提：

• 数组t是升序排序的
• 数组采用1-based下标（下标范围是1~n）

变量k的迭代规则 #

你可以把步长b的变化理解为从最高位到最低位逐位确定k的二进制值：

1. 初始状态下k=1，步长b从n/2开始，每次外层循环折半，直到b<1后停止外层循环
2. 对每一个固定的步长b，只要同时满足两个条件：
   • 跳b步之后不会超出数组上界（k+b <=n）
   • 跳步之后指向的元素仍然小于等于目标x（t[k+b] <=x）
     就把k往前跳b步
3. 所有步长遍历完成后，k就是数组中最后一个小于等于x的元素的下标，最后只要判断这个位置的元素是否等于x，就能确认目标是否存在。

为什么不会跳过目标元素 #

核心是整个搜索过程始终满足不变量：t[k] <=x，且所有大于当前k+b的位置都不可能是小于等于x的目标位置，逻辑推导如下：

• 初始状态k=1，只要t[1]<=x就符合不变量；如果连第一个元素都大于x，整个循环都不会跳步，最后判断t[1]!=x直接返回不存在，符合预期
• 对每个步长b，我们只会在t[k+b] <=x的时候才跳步，跳完之后新的k对应的元素仍然满足<=x的要求
• 步长从大到小折半，大的步长先把远的不可能区域排除，逐步缩小范围，每次跳的步长都是当前阶段最大的安全步长，不会跳过头：如果跳b步之后元素大于x，就会放弃这个步长，换更小的b尝试，不可能跳过比当前k大、但小于等于x的元素。

样例模拟 #

拿实际数值跑一遍逻辑会更清晰：
比如数组t = [0,2,3,5,7,8,9,10]（1-based存储，下标1到7对应值2到10，n=7），搜索目标x=8

1. 初始k=1，外层b初始为7/2=3
   • 检查k+b=1+3=4 <=7，t[4]=7 <=8，所以k +=3 →k=4
   • 再检查k+b=4+3=7 <=7，t[7]=10>8，停止内层循环
2. 外层b折半为1
   • 检查k+b=4+1=5 <=7，t[5]=8 <=8，所以k +=1 →k=5
   • 再检查k+b=5+1=6 <=7，t[6]=9>8，停止内层循环
3. 外层b折半为0，退出循环
4. 判断t[5]=8 ==x，成功找到目标，下标为5，结果正确。

和常规二分的对应关系 #

你熟悉的常规二分是用左右边界夹逼，这个变种是用二进制位拼接的思路找右边界：

• 常规二分每次取中间值判断，收缩左/右边界
• 这个实现每次确定k的二进制某一位要不要置1，本质和常规二分逻辑等价，时间复杂度同样是O(logn)。书里提到每个步长的while循环最多执行2次，原因是步长是折半的，同一个b最多跳1次就会要么超出数组范围，要么元素大于x，最多2次判断就会退出内层循环。

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