Repository navigation
Expand file tree
/
Copy pathSearch.java
More file actions
95 lines (80 loc) · 3.08 KB
/
Copy pathSearch.java
File metadata and controls
95 lines (80 loc) · 3.08 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
package ru.arhiser.search;
public class Search {
public static void main(String[] params) {
int[] array = new int[] {64, 42, 73, 41, 32, 53, 16, 24, 57, 42, 74, 55, 36};
bubbleSort(array);
System.out.println(arrayToString(array));
System.out.println(searchBinary(array, 16));
}
public static int searchLinear(int[] array, int elementToFind) {
for (int i = 0; i < array.length; i++) {
System.out.println("searhing at index: " + i + ", value: " + array[i]);
if (array[i] == elementToFind) {
System.out.println("found at index: " + i + ", value: " + array[i]);
return i;
}
}
System.out.println("not found: " + elementToFind);
return -1;
}
public static int searchBinary(int[] array, int elementToFind) {
int startIndex = 0;
int endIndex = array.length - 1;
int middleIndex;
while (startIndex <= endIndex) {
middleIndex = startIndex + (endIndex - startIndex) / 2;
System.out.println("startIndex: " + startIndex + ", endIndex: " + endIndex + ", middleIndex: " + middleIndex);
if (array[middleIndex] == elementToFind) {
System.out.println("found " + elementToFind + " at " + middleIndex);
return middleIndex;
}
if (array[middleIndex] > elementToFind) {
endIndex = middleIndex - 1;
} else {
startIndex = middleIndex + 1;
}
}
return -1;
}
public static int searchBinaryRecursive(int array[], int startIndex, int endIndex, int elementToFind) {
if (endIndex >= startIndex) {
int middleIndex = startIndex + (endIndex - startIndex) / 2;
if (array[middleIndex] == elementToFind) {
return middleIndex;
}
if (array[middleIndex] > elementToFind) {
return searchBinaryRecursive(array, startIndex, middleIndex - 1, elementToFind);
} else {
return searchBinaryRecursive(array, middleIndex + 1, endIndex, elementToFind);
}
}
return -1;
}
//System.out.println("startIndex: " + startIndex + ", endIndex: " + endIndex + ", middleIndex: " + middleIndex);
public static void bubbleSort(int[] array) {
boolean isSorted = false;
while (!isSorted) {
isSorted = true;
for (int i = 1; i < array.length; i++) {
if (array[i - 1] > array[i]) {
int tmp = array[i];
array[i] = array[i - 1];
array[i - 1] = tmp;
isSorted = false;
}
}
}
}
private static String arrayToString(int[] array) {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < array.length; i++) {
if (i > 0) {
sb.append(", ");
}
sb.append(array[i]);
}
sb.append("]");
return sb.toString();
}
}