001package algs11;
002import stdlib.*;
003import java.util.Arrays;
004
005/* ***********************************************************************
006 *  Compilation:  javac BinarySearch.java
007 *  Execution:    java BinarySearch whitelist.txt input.txt
008 *  Data files:   http://algs4.cs.princeton.edu/11model/tinyW.txt
009 *                http://algs4.cs.princeton.edu/11model/tinyT.txt
010 *                http://algs4.cs.princeton.edu/11model/largeW.txt
011 *                http://algs4.cs.princeton.edu/11model/largeT.txt
012 *
013 *  % java BinarySearch tinyW.txt tinyT.txt
014 *  50
015 *  99
016 *  13
017 *
018 *  % java BinarySearch largeW.txt largeT.txt
019 *  499569
020 *  984875
021 *  295754
022 *  207807
023 *  140925
024 *  161828
025 *  [3,675,966 total values]
026 *
027 *************************************************************************/
028public class BinarySearch {
029
030        // This is a simple rank function
031        // It works fine for small arrays
032        public static int rank0(double key, double[] a) {
033                for (int i = 0; i < a.length; i++)
034                        if (a[i] == key) return i;
035                return -1;
036        }
037
038        // Here is more efficient version, coded three ways
039        // precondition: array a[] is sorted
040        public static int rank(double key, double[] a) {
041                return rankHelper1 (key, a, 0, a.length - 1);
042        }
043
044        // Here is  a standard
045        public static int rankHelper1(double key, double[] a, int lo, int hi) {
046                // key is in a[lo..hi] or not present.
047                if (lo > hi) return -1;
048                int mid = lo + (hi - lo) / 2;
049                if      (key < a[mid]) return rankHelper1 (key, a, lo, mid - 1);
050                else if (key > a[mid]) return rankHelper1 (key, a, mid + 1, hi);
051                else return mid;
052        }
053
054        // This is the same, but uses a loop
055        public static int rankHelper2(double key, double[] a, int lo, int hi) {
056                while (lo <= hi) {
057                        // key is in a[lo..hi] or not present.
058                        int mid = lo + (hi - lo) / 2;
059                        if      (key < a[mid]) hi = mid - 1;
060                        else if (key > a[mid]) lo = mid + 1;
061                        else return mid;
062                }
063                return -1;
064        }
065
066        // This is the same, but written with explicit variables
067        public static int rankHelper3(double key, double[] a, int lo, int hi) {
068                if (lo > hi) return -1;
069                int result;
070                int mid = lo + (hi - lo) / 2;
071                if (key < a[mid])
072                        result = rankHelper3 (key, a, lo, mid - 1);
073                else if (key > a[mid])
074                        result = rankHelper3 (key, a, mid + 1, hi);
075                else
076                        result = mid;
077                return result;
078        }
079
080        public static void testTrace(String whitelistFile, int key) {
081                // get whitelist from file and sort
082                double[] whitelist = new In(whitelistFile).readAllDoubles();
083                Arrays.sort(whitelist);
084                StdOut.println(Arrays.toString(whitelist));
085
086                int rank = rank(key, whitelist);
087                if (rank >= 0) {
088                        StdOut.println(key + " is in the list");
089                } else {
090                        StdOut.println(key + " is NOT in the list");
091                }
092        }
093
094        public static void testInteractive(String whitelistFile) {
095                // get whitelist from file and sort
096                double[] whitelist = new In(whitelistFile).readAllDoubles();
097                Arrays.sort(whitelist);
098                StdOut.println(Arrays.toString(whitelist));
099
100                // read from the console; type Control-D or Control-Z at the beginning of a blank line to stop.
101                StdOut.print("Enter a number: ");
102                while (!StdIn.isEmpty()) {
103                        int key = StdIn.readInt();
104                        int rank = rank(key, whitelist);
105                        StdOut.format("%d %s in the list\n", key, (rank >= 0) ? "is" : "is not");
106                        StdOut.print("Enter a number: ");
107                }
108        }
109
110        public static void testPerformance(String whitelistFile, String keyFile) {
111                // get whitelist from file and sort
112                double[] whitelist = new In(whitelistFile).readAllDoubles();
113                Arrays.sort(whitelist);
114
115                // open key file and start timer
116                double[] keys = new In (keyFile).readAllDoubles();
117                Stopwatch sw = new Stopwatch();
118
119                // count number of data entries in the whitelist
120                int count = 0;
121                for (double key : keys) {
122                        if (rank0(key, whitelist) == -1) {
123                                //StdOut.println(key); // print to see the data, comment out for performance
124                                count = count + 1;
125                        }
126                }
127
128                StdOut.format ("%d misses\n%f seconds\n", count, sw.elapsedTime ());
129        }
130
131        public static void main(String[] args) {
132                testInteractive("data/tinyW.txt");
133                //testTrace("data/tinyW.txt", 28);
134                //testPerformance("data/tinyW.txt", "data/tinyT.txt");
135                //testPerformance("data/largeW.txt", "data/largeT.txt");
136                
137                // The following lines show why mid is computed as it is
138                //int hi = 2_000_000_010;
139                //int lo = 2_000_000_005;               
140                //StdOut.format ("(hi+lo)/2    = %,d\n", (hi+lo)/2);
141                //StdOut.format ("lo+(hi-lo)/2 = %,d\n", lo+(hi-lo)/2);
142                
143                // Similar things happen when using bit shifting
144                //StdOut.format ("(hi+lo)>>1   = %,d\n", (hi+lo)>>1);
145                //StdOut.format ("(hi+lo)>>>1  = %,d\n", (hi+lo)>>>1);
146        }
147}