forked from dr-cs/intro-oop-java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSearch.java
More file actions
124 lines (115 loc) · 4.67 KB
/
Search.java
File metadata and controls
124 lines (115 loc) · 4.67 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
import java.time.*;
import java.util.*;
import java.util.stream.*;
public class Search {
public static int linearSearch(Integer[] array, Integer value) {
for (int i = 0; i < array.length; i++) {
if (array[i] == value) { return i; }
}
return -1;
}
public static int binarySearchLoop(Integer[] array, int queryValue) {
int lo = 0, hi = array.length - 1;
while (lo <= hi) {
int middle = (lo + hi)/2;
if (array[middle] == queryValue) {
return middle;
}
if (array[middle] > queryValue) {
hi = middle - 1;
} else {
lo = middle + 1;
}
}
return -1;
}
public static int binarySearch(Integer[] array, int queryValue) {
return bsHelper(array, queryValue, 0, array.length - 1);
}
private static int bsHelper(Integer[] array, int queryValue, int lo, int hi) {
if (lo > hi) {
return -1;
}
int middle = (lo + hi)/2;
if (queryValue == array[middle]) {
return middle;
} else if (queryValue > array[middle]) {
return bsHelper(array, queryValue, middle + 1, hi);
} else {
return bsHelper(array, queryValue, lo, middle - 1);
}
}
public static <T> int binarySearch(T[] array, T queryValue,
Comparator<? super T> c) {
int lo = 0, hi = array.length - 1;
while (lo <= hi) {
int middle = (lo + hi)/2;
if (c.compare(array[middle], queryValue) == 0) {
return middle;
}
if (c.compare(array[middle], queryValue) > 0) {
hi = middle - 1;
} else {
lo = middle + 1;
}
}
return -1;
}
public static void main(String[] args) {
Random random = new Random();
int size = 2000000;
Integer[] randoms = Stream.generate(random::nextInt)
.limit(size)
.collect(Collectors.toList())
.toArray(new Integer[0]);
int queryValue = random.nextInt();
Instant start = Instant.now();
int index = linearSearch(randoms, queryValue);
Instant end = Instant.now();
System.out.printf("linearSearch of %d element array took %d ms%n",
size, Duration.between(start, end).toMillis());
start = Instant.now();
index = binarySearch(randoms, queryValue);
end = Instant.now();
System.out.printf("binarySearch of %d element array took %d ms%n",
size, Duration.between(start, end).toMillis());
// Integer[] ints = {4,7,5,6,3,9,2,1,8};
// System.out.println(Arrays.toString(ints));
// Arrays.sort(ints);
// System.out.println(Arrays.toString(ints));
// // When testing, test the edge cases
// System.out.println("Where is 4? " + binarySearchLoop(ints, 4));
// System.out.println("Where is 8? " + binarySearchLoop(ints, 8));
// System.out.println("Where is 5? " + binarySearchLoop(ints, 5));
// System.out.println("Now with recursive binarySearch:");
// System.out.println("Where is 4? " + binarySearch(ints, 4));
// System.out.println("Where is 8? " + binarySearch(ints, 8));
// System.out.println("Where is 5? " + binarySearch(ints, 5));
//
// GtStudent[] gtStuds = {
// new GtStudent("Von Neumann", Major.CMPE),
// new GtStudent("Sakaguchi", Major.CM),
// new GtStudent("Turing", Major.CS),
// new GtStudent("Bernoulli", Major.AE),
// new GtStudent("Maxwell", Major.EE),
// new GtStudent("Church", Major.CS),
// new GtStudent("Wright", Major.ARCH),
// new GtStudent("Sandiego", Major.IE)
// };
// System.out.println("Unsorted studs: " + Arrays.toString(gtStuds));
// Comparator<GtStudent> studComparator = new Comparator<GtStudent>() {
// public int compare(GtStudent a, GtStudent b) {
// if (!a.getMajor().equals(b.getMajor())) {
// return a.getMajor().compareTo(b.getMajor());
// } else {
// return a.getName().compareTo(b.getName());
// }
// }
// };
// Arrays.sort(gtStuds, studComparator);
// System.out.println("Sorted studs: " + Arrays.toString(gtStuds));
// GtStudent sandiego = new GtStudent("Sandiego", Major.IE);
// System.out.println("Where is Sandiego: "
// + binarySearch(gtStuds, sandiego, studComparator));
}
}