算法(4th ed)(57):基础——基础编程模型 3.10.1

阅读数:21 2019 年 10 月 30 日 07:03

算法(4th ed)(57):基础——基础编程模型 3.10.1

(二分查找:二分查找)

我们会在 3.2 节中详细学习二分查找算法,但此处先简单地描述一下。算法是由静态方法 rank() 实现的,它接受一个整数键和一个已经有序的int 数组作为参数。如果该键存在于数组中则返回它的索引,否则返回 -1。算法使用两个变量 lohi,并保证如果键在数组中则它一定在 a[lo..hi] 中,然后方法进入一个循环,不断将数组的中间键(索引为mid)和被查找的键比较。如果被查找的键等于 a[mid],返回 mid;否则算法就将查找范围缩小一半,如果被查找的键小于 a[mid] 就继续在左半边查找,如果被查找的键大于 a[mid] 就继续在右半边查找。算法找到被查找的键或是查找范围为空时该过程结束。二分查找之所以快是因为它只需检查很少几个条目(相对于数组的大小)就能够找到目标元素(或者确认目标元素不存在)。在有序数组中进行二分查找的示例如图 1.1.7 所示。

评论

发布