题目分析

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

看了两三遍不知道题目说啥,看了别人的答案以后才知道
第二句话的意思是:用二分查找法来找数组里面的一个数字,需要找几次才能找到.或者找几次才找不到

准备材料

算法第四版材料自带的素材,tiny作为白名单
把tinyW里面的每一个数字拿出来,去白名单里面找,是否存在于白名单
算法－第四版－练习1.2.9解答

原始代码

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

本题代码

package homework1_2;

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

import java.util.Arrays;

/**
 * @description: ${description}
 * @create: 2019-02-08
 **/
public class W_1_2_9 {
    public static int rank(int key, int[] a,Counter counter) {//增加传入参数
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            counter.increment();//每次查找的话,就要先找到一个中间点,那么就给次数+1
            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();
            Counter c=new Counter("times");//上面那行代码的意思是读取文件中的一个具体的数字,然后去白名单里面去找 是否有这个数字
            if (rank(key, whitelist,c) < 0) {
                StdOut.print(key);
                System.out.print(" is not in whitelist:");
                System.out.print("...how many times to find num not in whiteList:");
                System.out.print(c);
                System.out.println();
            }else {
                StdOut.print(key);
                System.out.print(" is in whitelist:");
                System.out.print("...how many times to find num in whiteList:");
                System.out.print(c);
                System.out.println();
            }
        }
    }
}

终端输入内容

F:\javalearn\ideacode\suanfa\src>javac homework1_2/W_1_2_9.java -Xlint
		homework1_2\W_1_2_9.java:29: 警告: [deprecation] In中的readInts(String)已过时
        int[] whitelist = In.readInts(args[0]);1 个警告
F:\javalearn\ideacode\suanfa\src>java homework1_2/W_1_2_9 tinyW.txt < tinyT.txt

控制台显示结果

23 is in whitelist:…how many times to find num in whiteList:3 times
50 is not in whitelist:…how many times to find num not in whiteList:4 times
10 is in whitelist:…how many times to find num in whiteList:4 times
99 is not in whitelist:…how many times to find num not in whiteList:4 times
18 is in whitelist:…how many times to find num in whiteList:4 times
23 is in whitelist:…how many times to find num in whiteList:3 times
98 is in whitelist:…how many times to find num in whiteList:4 times
84 is in whitelist:…how many times to find num in whiteList:3 times
11 is in whitelist:…how many times to find num in whiteList:3 times
10 is in whitelist:…how many times to find num in whiteList:4 times
48 is in whitelist:…how many times to find num in whiteList:4 times
77 is in whitelist:…how many times to find num in whiteList:4 times
13 is not in whitelist:…how many times to find num not in whiteList:4 times
54 is in whitelist:…how many times to find num in whiteList:3 times
98 is in whitelist:…how many times to find num in whiteList:4 times
77 is in whitelist:…how many times to find num in whiteList:4 times
77 is in whitelist:…how many times to find num in whiteList:4 times
68 is in whitelist:…how many times to find num in whiteList:2 times

解题心得

1.看不懂题目,可能是理解问题或者是英文翻译的问题
2.看懂了题目然后就要通过数学思维把问题抽象化,编程化
3.如何把结果正确的展示出来
4.关键计数器放在哪里取决于什么时候清零.什么时候加一

算法－第四版－练习1.2.9解答