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}