§05 查找
二分查找
折半查找针对有序表：每轮取区间中点与目标比较，相等即命中；目标小于中点就只查左半， 大于则只查右半，查找区间每轮缩小一半。比较 ⌈log₂(n+1)⌉ 次以内必然出结果。
二分查找
伪代码
1
procedure binarySearch(a, n, x)
2
low = 1; high = n
3
while low <= high do
4
mid = (low + high) / 2（向下取整）
5
if x = a[mid] then
6
return mid // 查找成功
7
else if x < a[mid] then
8
high = mid - 1 // 到左半区
9
else
10
low = mid + 1 // 到右半区
11
end if
12
end while
13
return 0 // 查找失败
14
end procedure