Binary Search 二元搜寻常见问题

Binary Search 二元搜寻常见问题
Categories:
Tags:

中间指标切分点算法

索引 0 1 2 3 4 5 6 7 8 9
指标位置 左指标 右指标

取中间偏左的数字

  • 中间指标 左方数字 个数 小于或等于 右方数字 个数

公式：

  • (左指标 + 右指标) / 2，无条件捨去
  • 左指标 + (右指标 - 左指标) / 2，无条件捨去
// 公式 1
let middleNumberPointer = Math.floor((rightNumberPointer + leftNumberPointer) / 2);
// 公式 2
let middleNumberPointer = leftNumberPointer + Math.floor((rightNumberPointer - leftNumberPointer) / 2);

偶数阵列

中间指标 左方数字 个数 小于 右方数字 个数

e.g. [0,1,2,3,4,5,6,7,8,9]

  • (0 + 9) / 2 = 4.5，无条件捨去为 4
  • 0 + (9 - 0) / 2 = 4.5，无条件捨去为 4
索引 0 1 2 3 4 5 6 7 8 9
指标位置 左指标 中间指标 右指标

奇数阵列

中间指标 左方数字 个数 等于 右方数字 个数

e.g. [0,1,2,3,4,5,6,7,8]

  • (0 + 8) / 2 = 4，无条件捨去为 4
  • 0 + (8 - 0) / 2 = 4，无条件捨去为 4
索引 0 1 2 3 4 5 6 7 8
指标位置 左指标 中间指标 右指标

while 迴圈判断式 left <= right

区间定义

索引 0 1 2 3 4 5 6 7 8 9 说明
[3, 5] 闭区间 3 4 5 闭区间 [x, y]：包含 x, y
(4, 9) 开区间 5 6 7 8 开区间 (x, y)：不包含 x, y
[1, 6) 左闭右开区间 1 2 3 4 5 左闭右开区间 [x, y)：包含 x, 不包含 y

Binary Search 的写法中的 left 与 right 代表的就是：答案还有可能存在的区间的两端点，这是个 闭区间 [x, y]

所以当 left == right 的时候，代表可能答案会在 [3,3] 之间，且区间裡只有 1 个元素，但不确定这个元素是不是要找的答案，所以要再判断一次

因此 while 的判断式会是 <= 而非 <。

中间指标移动方式，为什麽是 right = mid - 1 跟 left = mid + 1

因为我们要的答案是 闭区间，假如 mid 不是答案，那 mid 必须被排除，需要直接捨弃

当要的答案在左侧，则会用 [left, mid-1] 当作新的区间，左边指标不动，移动右侧指标

当要的答案在右侧，则会用 [mid+1, right] 当作新的区间，右边指标不动，移动左侧指标

参考资料