失去的时间…

How much I spend on meaningless approaches to learn algorithms comes back to me now.

二分查找

Java实现(int数组实现)

因为还不知道Java里泛型咋写, 所以用int数组实现…

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) >> 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){
        In in = new In(args[0]);
        int[] whitelist = in.readAllInts();
        Arrays.sort(whitelist);
        while(!StdIn.isEmpty()){
            int key = StdIn.readInt();
            if(rank(key,whitelist)<0)
                StdOut.println(key);
        }
    }
}