Skip to content

Commit c6022a5

Browse files
author
Yiwei Liu
committed
searching
1 parent 7c13382 commit c6022a5

File tree

12 files changed

+131
-20
lines changed

12 files changed

+131
-20
lines changed

‎src/main/java/com/openmind/searching/BaseSearchProcess.java

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package com.openmind.searching;
2+
3+
public abstract class BaseSearchProcess {
4+
5+
protected abstract int search(int[] a, int key);
6+
7+
protected int[] customerArray() {
8+
return null;
9+
}
10+
11+
static int[] genRandomArray(int count) {
12+
if (count <= 0) {
13+
count = 7;
14+
}
15+
16+
int[] origin = new int[count];
17+
for (int i = 0; i < count; i++) {
18+
origin[i] = (int) (Math.random() * 100);
19+
}
20+
return origin;
21+
}
22+
23+
protected static void printArray(int[] origin) {
24+
for (int t : origin) {
25+
System.out.print(t + " ");
26+
}
27+
System.out.println();
28+
}
29+
30+
public void proceeding(int n, int key) {
31+
int[] a = customerArray() == null ? genRandomArray(n) : customerArray();
32+
System.out.print("Origin: ");
33+
printArray(a);
34+
35+
final int indices = search(a, key);
36+
System.out.printf("search indices of %s: %s", key, indices);
37+
}
38+
39+
}

‎src/main/java/com/openmind/searching/BinarySearch.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.openmind.searching;
2+
3+
import java.util.Arrays;
4+
5+
public class BinarySearch extends BaseSearchProcess {
6+
7+
8+
@Override
9+
protected int search(int[] a, int key) {
10+
//check start
11+
System.out.printf("check indices of %s: %s \n", key, Arrays.binarySearch(a, key));
12+
//check end
13+
14+
int min = 0, max = a.length - 1, mid = (min + max) / 2;
15+
while (min <= max) {
16+
if (key == a[mid]) {
17+
return mid;
18+
}
19+
20+
if (key < a[mid]) {
21+
max = mid - 1;
22+
} else {
23+
min = mid + 1;
24+
}
25+
26+
mid = (min + max) / 2;
27+
28+
}
29+
return -1;
30+
}
31+
32+
@Override
33+
protected int[] customerArray() {
34+
int[] sorted = new int[]{55, 31, 34, 64, 48, 95, 27, 13, 74, 65};
35+
Arrays.sort(sorted);
36+
return sorted;
37+
}
38+
39+
public static void main(String[] args) {
40+
final BinarySearch search = new BinarySearch();
41+
search.proceeding(10, 74);
42+
System.out.println();
43+
search.proceeding(10, -74);
44+
}
45+
}

‎src/main/java/com/openmind/searching/LinearSearch.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package com.openmind.searching;
2+
3+
public class LinearSearch extends BaseSearchProcess {
4+
5+
6+
@Override
7+
protected int search(int[] a, int key) {
8+
for (int i = 0; i < a.length; i++) {
9+
if (a[i] == key) {
10+
return i;
11+
}
12+
}
13+
return -1;
14+
}
15+
16+
@Override
17+
protected int[] customerArray() {
18+
return new int[]{55, 31, 34, 64, 48, 95, 27, 13, 74, 65};
19+
}
20+
21+
public static void main(String[] args) {
22+
23+
final LinearSearch search = new LinearSearch();
24+
search.proceeding(10, 27);
25+
System.out.println();
26+
search.proceeding(10, 7);
27+
}
28+
}

‎src/main/java/com/openmind/sort/BaseSortProcess.java renamed to ‎src/main/java/com/openmind/sorting/BaseSortProcess.java

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
1-
package com.openmind.sort;
1+
package com.openmind.sorting;
22

33
import java.util.Arrays;
4-
import java.util.stream.Stream;
54

65
public abstract class BaseSortProcess {
76

‎src/main/java/com/openmind/sort/MergeSort.java renamed to ‎src/main/java/com/openmind/sorting/MergeSort.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
1-
package com.openmind.sort;
1+
package com.openmind.sorting;
22

33
/**
4-
* Merge sort : ascedning
4+
* Merge sorting : ascedning
55
* CPU complexity: O(nlogn) O(nlogn) O(nlogn)
66
* Mem complexity: O(n)
77
**/

‎src/main/java/com/openmind/sort/RadixSort.java renamed to ‎src/main/java/com/openmind/sorting/RadixSort.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.openmind.sort;
1+
package com.openmind.sorting;
22

33
/**
44
* Radix Sort: ascending

‎src/main/java/com/openmind/sort/insertion/InsertionSort.java renamed to ‎src/main/java/com/openmind/sorting/insertion/InsertionSort.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,11 @@
1-
package com.openmind.sort.insertion;
1+
package com.openmind.sorting.insertion;
22

3-
import com.openmind.sort.BaseSortProcess;
3+
import com.openmind.sorting.BaseSortProcess;
44

55
public class InsertionSort extends BaseSortProcess {
66

77
// @Override
8-
// int[] sort(int[] a) {
8+
// int[] sorting(int[] a) {
99
// int n = a.length, count = 0, pos, current;
1010
// for (int i = 1; i < n; i++) {
1111
// pos = i;

‎src/main/java/com/openmind/sort/insertion/ShellSort.java renamed to ‎src/main/java/com/openmind/sorting/insertion/ShellSort.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
1-
package com.openmind.sort.insertion;
1+
package com.openmind.sorting.insertion;
22

3-
import com.openmind.sort.BaseSortProcess;
3+
import com.openmind.sorting.BaseSortProcess;
44

55
/**
66
* Shell Sort: ascending , Diminishing Increment Sort
@@ -17,7 +17,7 @@ protected int[] sort(int[] a) {
1717
//(n/2, n/2/2, ..., 1)
1818
for (int gap = n / 2; gap > 0; gap /= 2) {
1919

20-
//insertion sort
20+
//insertion sorting
2121
for (int i = gap; i < n; i++) {
2222
int j = i, tmp = a[j];
2323
while (j - gap >= 0 && tmp < a[j - gap]) {

‎src/main/java/com/openmind/sort/selection/HeapSort.java renamed to ‎src/main/java/com/openmind/sorting/selection/HeapSort.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
1-
package com.openmind.sort.selection;
1+
package com.openmind.sorting.selection;
22

3-
import com.openmind.sort.BaseSortProcess;
3+
import com.openmind.sorting.BaseSortProcess;
44

55
/**
6-
* Heap sort : ascending
6+
* Heap sorting : ascending
77
* CPU complexity: O(nlogn) O(nlogn) O(nlogn)
88
* Mem complexity: O(1)
99
*/

‎src/main/java/com/openmind/sort/selection/SelectionSort.java renamed to ‎src/main/java/com/openmind/sorting/selection/SelectionSort.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
1-
package com.openmind.sort.selection;
1+
package com.openmind.sorting.selection;
22

3-
import com.openmind.sort.BaseSortProcess;
3+
import com.openmind.sorting.BaseSortProcess;
44

55
/**
66
* Selection Sort: ascending

0 commit comments

Comments
 (0)