【算法】1.1. 基础编程模型

正文

二分查找与白名单过滤

想象一家信用卡公司，它需要检查客户的交易账号是否有效。为此，它需要：

• 将客户的账号保存在一个文件中，我们称它为“白名单”；
• 从标准输入中得到每笔交易的账号；
• 在标准输出中打印所有与任何客户无关的账号，公司很可能拒绝此类交易。

在一家有上百万客户的大公司中，需要处理数百万甚至更多的交易都是很正常的。暴力实现处理大量输入（比如含有 100 万个条目的白名单和 1000 万条交易）非常慢。没有如二分查找或者归并排序这样的高效算法，解决大规模的白名单问题是不可能的。

以下是示例程序：

package ch1;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

/**
 * Created by plough on 2018/4/1.
 */
public class BinarySearch {
    public static int rand(int key, int[] a) {
        // 数组必须是有序的
        int lo = 0;
        int hi = a.length - 1;
        while (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 (rand(key, whitelist) < 0) {
                StdOut.println(key);
            }
        }
    }
}

答疑

• Java字节码是程序的一种低级表示，可以运行于Java的虚拟机。将程序抽象为字节码可以保证Java程序员的代码能够运行在各种设备之上。
• 我们会使用int类型表示较小的数（小于10个十进制位）而使用long表示10亿以上的数。
• Math.abs(-2145483648) 的返回值还是 -2145483648。这个奇怪的结果（但的确是真的）就是整数溢出的典型例子。
• 如何才能将一个double变量初始化为无穷大？使用Java内置常数：Double.POSITIVE_INFINITY 和 Double.NEGATIVE_INFINITY。
• Java表达式1/0和1.0/0.0的值是什么？第一个表达式会产生一个运行时除以零异常（它会终止程序）；第二个表达式的值是Infinity（无穷大）。
• 负数的除法和余数的结果是什么？表达式a/b的商会向0取整；a%b的余数的定义是(a/b)*b + a%b恒等于a。例如-14/3和14/-3的商都是-4，但-14%3是-2，而14%-3是2。
• 一个 for 循环和它的 while 形式有什么区别？for 循环头部的代码和 for 循环的主题代码在同一个代码段之中。在一个典型的 for 循环中，递增变量一般在循环结束之后都是不可用的；但在和它等价的 while 循环中，递增变量在循环结束之后仍然是可用的。这个区别常常是使用 while 而非 for 循环的主要原因。