forked from destiny1020/algorithm_playground
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSorts.java
More file actions
125 lines (109 loc) · 2.4 KB
/
Sorts.java
File metadata and controls
125 lines (109 loc) · 2.4 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
package gadget;
public class Sorts
{
// Binary Search, the array should be ordered
public static int binarySearch(int key, int[] array)
{
int hi = array.length - 1;
int lo = 0;
int mid;
while(lo <= hi)
{
mid = (lo + hi) / 2;
if(key == array[mid])
{
return mid;
}
if(key < array[mid])
{
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
return -1;
}
// Range Binary Search, lo = 0, hi = length - 1
public static int binarySearch(int key, int[] array, int lo, int hi)
{
int mid;
while(lo <= hi)
{
mid = (lo + hi) / 2;
if(key == array[mid])
{
return mid;
}
if(key < array[mid])
{
hi = mid - 1;
}
else
{
lo = mid + 1;
}
}
return -1;
}
// Extended Binary Search, return two values: [index, count]
public static int[] binarySearchExtend(int key, int[] array)
{
int[] results = new int[]{-1, -1};
results[0] = binarySearch(key, array);
int count;
if (results[0] >= 0)
{
count = 1;
int index = results[0];
while (index > 0 && array[--index] == key)
{
count++;
}
index = results[0];
while (index < array.length - 1 && array[++index] == key)
{
count++;
}
results[1] = count;
}
return results;
}
// Recursive Binary search
public static int recursiveBinarySearch(int key, int[] array)
{
return recursiveBinarySearch(key, array, 0, array.length - 1);
}
// Recursive Binary search and keep deep info
public static int recursiveBinarySearchWithDeep(int key, int[] array)
{
return recursiveBinarySearch(key, array, 0, array.length - 1, 1);
}
private static int recursiveBinarySearch(int key, int[] array, int lo, int hi)
{
if(lo > hi)
return -1;
int mid = (lo + hi) / 2;
if(key == array[mid])
return mid;
if(key < array[mid])
return recursiveBinarySearch(key, array, lo, mid - 1);
else
return recursiveBinarySearch(key, array, mid + 1, hi);
}
// Keep record of recursive deep and print arguments
private static int recursiveBinarySearch(int key, int[] array, int lo, int hi, int deep)
{
System.out.println("Current Deep: " + deep + "\tLow: " + lo + "\tHigh: " + hi);
if(lo > hi)
return -1;
int mid = (lo + hi) / 2;
if(key == array[mid])
return mid;
if(key < array[mid])
return recursiveBinarySearch(key, array, lo, mid - 1, ++deep);
else
return recursiveBinarySearch(key, array, mid + 1, hi, ++deep);
}
}