BinarySearch.java
4.52 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/******************************************************************************
* Compilation: javac BinarySearch.java
* Execution: java BinarySearch whitelist.txt < input.txt
* Dependencies: In.java StdIn.java StdOut.java
* Data files: http://algs4.cs.princeton.edu/11model/tinyW.txt
* http://algs4.cs.princeton.edu/11model/tinyT.txt
* http://algs4.cs.princeton.edu/11model/largeW.txt
* http://algs4.cs.princeton.edu/11model/largeT.txt
*
* % java BinarySearch tinyW.txt < tinyT.txt
* 50
* 99
* 13
*
* % java BinarySearch largeW.txt < largeT.txt | more
* 499569
* 984875
* 295754
* 207807
* 140925
* 161828
* [367,966 total values]
*
******************************************************************************/
package edu.princeton.cs.algs4;
import java.util.Arrays;
/**
* The {@code BinarySearch} class provides a static method for binary
* searching for an integer in a sorted array of integers.
* <p>
* The <em>indexOf</em> operations takes logarithmic time in the worst case.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/11model">Section 1.1</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class BinarySearch {
/**
* This class should not be instantiated.
*/
private BinarySearch() { }
/**
* Returns the index of the specified key in the specified array.
*
* @param a the array of integers, must be sorted in ascending order
* @param key the search key
* @return index of key in array {@code a} if present; {@code -1} otherwise
*/
public static int indexOf(int[] a, int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
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;
}
/**
* Returns the index of the specified key in the specified array.
* This function is poorly named because it does not give the <em>rank</em>
* if the array has duplicate keys or if the key is not in the array.
*
* @param key the search key
* @param a the array of integers, must be sorted in ascending order
* @return index of key in array {@code a} if present; {@code -1} otherwise
* @deprecated Replaced by {@link #indexOf(int[], int)}.
*/
@Deprecated
public static int rank(int key, int[] a) {
return indexOf(a, key);
}
/**
* Reads in a sequence of integers from the whitelist file, specified as
* a command-line argument; reads in integers from standard input;
* prints to standard output those integers that do <em>not</em> appear in the file.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
// read the integers from a file
In in = new In(args[0]);
int[] whitelist = in.readAllInts();
// sort the array
Arrays.sort(whitelist);
// read integer key from standard input; print if not in whitelist
while (!StdIn.isEmpty()) {
int key = StdIn.readInt();
if (BinarySearch.indexOf(whitelist, key) == -1)
StdOut.println(key);
}
}
}
/******************************************************************************
* Copyright 2002-2016, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/