-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSparseSearch.java
More file actions
67 lines (62 loc) · 1.89 KB
/
SparseSearch.java
File metadata and controls
67 lines (62 loc) · 1.89 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
package algorithm.search;
public class SparseSearch {
public static boolean modifiedBinarySearch(String[] array, int low, int high, String target) {
if (low > high)
return false;
int mid = (low + high) / 2;
//Modified Binary Search
if (array[mid] == "") {
int i = mid - 1;
int j = mid + 1;
while (true) {
if (i < low && j > high)
return false;
if (i >= low && array[i] != "") {
mid = i;
break;
} else if (j <= high && array[j] != "") {
mid = j;
break;
}
i--;
j++;
}
}
// Now perform simple Binary Search
if (array[mid].equals(target))
return true;
else if (array[mid].compareTo(target) > 0)
return modifiedBinarySearch(array, low, mid - 1, target);
else
return modifiedBinarySearch(array, mid + 1, high, target);
}
public static boolean searchForString(String[] array, String target) {
return modifiedBinarySearch(array, 0, array.length - 1, target);
}
public static void main(String args[]) {
String[] array = {
"",
"educative",
"",
"",
"",
"hello",
"",
"learning",
"world",
"",
"",
""
};
String[] targetArray = {
"educative",
"learning",
"good",
"bad",
" "
};
for (int i = 0; i < targetArray.length; i++) {
System.out.println(targetArray[i] + ": " + searchForString(array, targetArray[i]));
}
}
}