算法(4th ed)(56):基础——基础编程模型 3.10

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

算法(4th ed)(56):基础——基础编程模型 3.10

(二分查找)

我们要学习的第一个 Java 程序的示例程序就是著名、高效并且应用广泛的二分查找算法,如下所示。这个例子将会展示本书中学习新算法的基本方法。和我们将要学习的所有程序一样,它既是算法的准确定义,又是算法的一个完整的 Java 实现,而且你还能够从本书的网站上下载它。

二分查找

复制代码
import java.util.Arrays;
public class BinarySearch
{
public static int rank(int key, int[] a)
{ // 数组必须是有序的
int lo = 0;
int hi = a.length - 1;
while (lo <= hi)
{ // 被查找的键要么不存在,要么必然存在于 a[lo..hi] 之中
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
public static void main(String[] args)
{
int[] whitelist = In.readInts(args[0]);
Arrays.sort(whitelist);
while (!StdIn.isEmpty())
{ // 读取键值,如果不存在于白名单中则将其打印
int key = StdIn.readInt();
if (rank(key, whitelist) < 0)
StdOut.println(key);
}
}
}

这段程序接受一个白名单文件(一列整数)作为参数,并会过滤掉标准输入中的所有存在于白名单中的条目,仅将不在白名单上的整数打印到标准输出中。它在rank() 静态方法中实现了二分查找算法并高效地完成了这个任务。关于二分查找算法的完整讨论,包括它的正确性、性能分析及其应用,请见 3.1 节。

复制代码
% java BinarySearch tinyW.txt < tinyT.txt
50
99
13

评论

发布