算法技术手册（原书第2 版）

94

｜

第

5

章

if t < A[mid] then

high = mid - 1

else if t > A[mid] then

low = mid + 1

else

return true

return false

❸

end

❶

如果还存在可以搜索的范围，继续循环。

❷

中点的值要取整。

❸

“衍生算法”一节（

5.3.5

节）将会讨论如何支持“搜索

/

插入”操作。

5.2.3 解决方案

例

5-3

的

Java

代码是一个泛型的二分搜索实现，它接受一个有序的数组集合。

Java

中的

java.util.Comparable<T>

接口提供了方法

compareTo

。一个类只需要正确实现该方法，

就能保证该类实例的有序性。

例

5-3

：二分搜索的

Java

实现

/**

*

二分搜索处理一个泛型的有序数组

*

* @param T

集合中的元素类型，这个类型必须实现了

Comparable

接口

*/

public class BinarySearch<T extends Comparable<T>> {

/*

在集合中查找非空元素，若成功，则返回

true */

public boolean search(T[] collection, T target) {

if (target == null) { return false; }

int low = 0, high = collection.length - 1;

while