1800字普林斯顿大学课程浓缩笔记：程序员必知的算法之查找和排序算法

 1public class Questions {
 2
 3    // invariant: answer is in [lo, hi)
 4    public static int search(int lo, int hi) {
 5        if ((hi - lo) == 1) return lo;
 6        int mid = lo + (hi - lo) / 2;
 7        StdOut.printf("Is it less than %d?  ", mid);
 8        if (StdIn.readBoolean()) 
 9            return search(lo, mid);
10        else                     
11            return search(mid, hi);
12    }
13
14    public static void main(String[] args) {
15        int k = Integer.parseInt(args[0]);
16        int n = (int) Math.pow(2, k);
17        StdOut.printf("Think of an integer between %d and %d\n", 0, n-1);
18        int secret = search(0, n);
19        StdOut.printf("Your number is %d\n", secret);
20    }
21
22}

 1public class Binary { 
 2    public static void main(String[] args) { 
 3
 4        // read in the command-line argument
 5        int n = Integer.parseInt(args[0]);
 6
 7        // set power to the largest power of 2 that is <= n
 8        int power = 1;
 9        while (power <= n/2) {
10            power *= 2;
11        }
12
13        // check for presence of powers of 2 in n, from largest to smallest
14        while (power > 0) {
15
16            // power is not present in n 
17            if (n < power) {
18                System.out.print(0);
19            }
20
21            // power is present in n, so subtract power from n
22            else {
23                System.out.print(1);
24                n -= power;
25            }
26
27            // next smallest power of 2
28            power /= 2;
29        }
30
31        System.out.println();
32
33    }
34
35}

 1import java.util.Arrays;
 2
 3public class BinarySearch {
 4
 5    // return the index of the key in the sorted array a[]; -1 if not found
 6    public static int search(String key, String[] a) {
 7        return search(key, a, 0, a.length);
 8    }
 9    public static int search(String key, String[] a, int lo, int hi) {
10System.out.println("lo  = " + lo);
11System.out.println("hi  = " + hi);
12        // possible key indices in [lo, hi)
13        if (hi <= lo) return -1;
14        int mid = lo + (hi - lo) / 2;
15        int cmp = a[mid].compareTo(key);
16        if      (cmp > 0) return search(key, a, lo, mid);
17        else if (cmp < 0) return search(key, a, mid+1, hi);
18        else              return mid;
19    }
20
21
22    // whitelist, exception filter
23    public static void main(String[] args) {
24        In in = new In(args[0]);
25        String s = in.readAll();
26        String[] words = s.split("\\s+");
27        System.err.println("Done reading words");
28
29        // sort the words (if needed)
30        Arrays.sort(words);
31        System.err.println("Done sorting words");
32
33        // prompt user to enter a word and check if it's there
34        while (!StdIn.isEmpty()) {
35            String key = StdIn.readString();
36            if (search(key, words) < 0) StdOut.println(key);
37        }
38    }
39}