Binary Search(二分搜索)

转载请注明出处 leonchen1024.com/2018/08/14/…

二分搜索(binary search),也叫做折半搜索(half-interval search),对数搜索(logarithmic search),对半搜索(binary chop),是一种在有序数组中查找某一特定元素的搜索算法.

二分搜索有几个变体.特别是,分散层叠(fractional cascading)(将每个数组里的值集合成一个数组,元素为11[0,3,2,0] 的形式,括号内的数字是该值在对应数组中应该返回的数字)提高了在多个数组中查找相同值的效率,高效的解决了一系列计算几何和其他领域的查找问题).指数查找(Exponential search)延伸了二分查找到一个没有边界的 list.binary search tree和B-tree是基于 binary search 延伸的.

原理

搜索时从数组中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果中间元素大于或者小于要查找的元素,则在数组中大于或者小于查找元素的一半中继续查找,重复这个过程直到找到这个元素,或者这一半的大小为空时则代表找不到.这样子每一次比较都使得搜索范围缩小一半.

步骤

给定一个有序数组 A 是 A0,...,An-1并保证 A0<=...<=An-1,以及目标值 T.

令 L 为0,R 为 n-1.
如果 L>R 则搜索失败
令m(中间值元素索引)为最大的小于(L+R)/2的整数
如果 Am<T ,令 L=m+1并回到第2步;
如果 Am>T ,令 R=m-1并回到第2步;
当 Am=T,搜索结束;T 所在的索引位置为m.

变体

令 L 为0,R 为 n-1.
令 m(中间元素索引) 为上限,也就是最小的大于(L+R)/2的值.
如果 Am>T ,设置 R 为 m-1并且返回第2步
如果 Am<=T ,设置 L 为m 并且返回第2步.
直到 L=R ,搜索完成.这时候如果T=Am,返回 m,否则,搜索失败.

转载请注明出处 leonchen1024.com/2018/08/14/…

在 Am<=T 的时候,这个变体将 L 设置为 m 而不是 m+1.这个方式的比较是更快速的,因为它在每个循环里省略了一次比较.但是平均就会多出来一次循环.在数组包含重复的元素的时候这个变体总是会返回最右侧的元素索引.比如 A 是[1,2,3,4,4,5,6,7]查找的对象是4,那么这个方法会返回 index 4,而不是 index 3.

大致匹配

由于有序数组的顺序性,可以将二分搜索扩展到大致匹配.可以用来计算赋值的排名(或称秩,比它更小的元素的数量),前趋(下一个最小元素),后继(下一个最大元素)以及最近邻.还可以使用两个排名查询来执行范围查询.

排名查询可以使用调整后的二分搜索来进行.成功时返回m,失败时返回 L, 这样就等于返回了比目标值小的元素数目.
前趋和后继可以使用排名查询来进行.当知道目标值的排名,成功时前趋是排名位置的上一个元素,失败时则是排名位置的元素.它的后继是排名位置的后一个元素,或是前趋的下一个元素.目标值的最近领可能是前趋或后继,取决于哪个更接近目标值.
范围查询,一旦知道范围两边的值的排名,那么大于边界最小值且小于边界最大值的元素排名就是他们的范围,是否包含边界值根据需要处理.

性能分析

时间复杂度 二分查找每次把搜索区域减少一半,时间复杂度为

(n 是集合中元素的个数) 最差的情况是遍历到最后一层,或者是没有找到该元素的时候,复杂度为 $O(\lfloor log_2 n + 1 \rfloor)$ .

综合复杂度为 $O(log_2 n)$

分散层叠(fractional cascading) 可以提高在多数组中查询相同值的效率. k 是数组的数量,在每个数组中查询目标值消耗 $O(k log n)$ 的时间.分散层叠可以将它降低到 $O(k+log n)$ .

变体效率分析 相对于正常的二分搜索,它减少了每次循环的比对次数,但是它必须做完完整的循环,而不会在中间就得到答案.但是在 n 很大的情况下减少了对比次数的提升不能够抵消多余的循环的消耗.

转载请注明出处