《算法第四版》课后练习题1.2.9答案

习题1.2.9

修改 BinarySearch（请见 1.1.10.1 节中的二分查找代码），使用 Counter 统计在有查找中被检查的键的总数并在查找全部结束后打印该值。提示：在 main() 中创建一个 Counter 对象并将它作为参数传递给 rank()。

要点分析

1.  BinarySearch

1.1.10.1 节中的二分查找代码在课本第28页，代码如下：

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

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) {
            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);
            }
        }
    }
}

2.  Counter

关于Counter类的具体介绍可以查看课本第39页，这里给出该类的API

3.  解题思路

根据该题的提示，我们可以需要修改rank()方法的参数，将一个Counter对象传给rank，然后用increment()方法进行统计次数就可以了。

值得注意的是，在main方法中，Counter要在while循环里生成对象，否则计数器会随着每次查找值而累加。

参考答案

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


public class BinarySearch {
    public static int rank(int key, int[] a, Counter c) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            c.increment();
            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]);

//        Counter c = new Counter("Test");  //不可以放在这里，因为每次查找Counter计数器值没有被清零会累加
        System.out.println("请输入要查找的值:");
        while (!StdIn.isEmpty()) {
            int key = StdIn.readInt();
            Counter c = new Counter("Test");
            int r = rank(key, whitelist, c);
            if (r < 0) {
                StdOut.println("没找到");
            } else {
                System.out.println("被检查的键的总数为:" + c.tally()+ ", 下标为 " + r);
            }
            System.out.println("请输入要查找的值:");
        }
    }
}


args[0]传入一个文本文档地址，比如E:\Test\Test.txt
Text.txt中的内容为1 3 2 4 6 5 7 9 8
则输出:
请输入要查找的值:
9
被检查的键的总数为:3, 下标为 7
请输入要查找的值:
6
被检查的键的总数为:1, 下标为 4
请输入要查找的值:
0
没找到