Question

二分搜索算法是利用什么实现的算法?

Answer 1

二分搜索算法是利用删减实现的算法。

二分搜索的搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

二分搜索算法的应用

二分搜索是一种在有序数组中查找某一特定元素的搜索算法，这种搜索算法每一次比较都使搜索范围缩小一半。不过，因为有序数组的顺序性，将二分搜索算法扩展到能适用大致匹配并不是很重要。

举例来说，二分搜索算法可以用来计算一个赋值的排名（或称秩，比它更小的元素的数量）、前趋（下一个最小元素）、后继（下一个最大元素）以及最近邻。搜索两个值之间的元素数目的范围查询可以借由两个排名查询（又称秩查询）来运行。

假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。