# 二分查找为什么每次排除一半

By DUSK

Topic: Computing, AI & Electronics

[Open the interactive Jig](https://ask.jig.com/j/3OrVWDEKNC7R)

## Guide

### 1. 排好序的一排数字

陈列台上有 15 个数字方块，从小到大排好了队。二分查找只在排好序的数据里才管用，搜索过程中我们绝不重新排序。前面的 low 和 high 两个标记，圈出目标还可能藏身的范围。

这些数字是随意挑的示例；方块大小和间距只是示意。

### 2. 比一次，排除一半

要找 60，先看正中间的方块 mid：它是 38。38 比 60 小，它左边的数只会更小，所以 mid 和左边的方块一起被推到后排。候选一下子从 15 个变成 7 个。

被排除的是 mid 本身加上整整一侧，所以每次都排除一半以上。

### 3. 一路缩小，直到找到

找 47：第 1 次和 38 比，往右；第 2 次和 60 比，往左；第 3 次正好碰到 47。每比一次，low 或 high 就跳到 mid 的旁边，范围越收越窄。

台子右前方的小灯记录比较次数，这次亮了 3 盏。

### 4. 找不到时，范围会变空

找 50：它根本不在队伍里。比完 4 次后，low 跑到了 high 的右边，范围里一个数也不剩，这时就能肯定地说它不存在。所以二分查找并不是每一步都能找到目标。

停下时 low 正好指着 50 该插入的位置：47 和 53 之间。

### 5. 两头的边界

目标在最左端或最右端时，范围要一路缩到边上。mid 依次落在第 7、3、1、0 号（或 7、11、13、14 号）方块，第 4 次比较才找到。边界既没有漏掉，也没有越界。

### 6. 自己试一试

在右侧面板挑一个目标，或直接点一个方块；标着“不存在”的是队伍里没有的数。按“单步”看一次比较，按“播放”一路走到底，按“重置”重新开始。

一句话总结：每和中间比一次，就能排除一半以上的候选，所以 15 个数最多比 4 次。