-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsearchAlgorithm.java
More file actions
167 lines (137 loc) · 4.31 KB
/
searchAlgorithm.java
File metadata and controls
167 lines (137 loc) · 4.31 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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
package algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author zhongshanhuang
* @company caih
* @email [email protected]
* @create 2019-08-09 15:00
*/
public class searchAlgorithm {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 6, 6, 9};
// System.out.println(Search.seqSearch(arr, 8));
// System.out.println(Search.binarySearch(arr, 0, arr.length - 1, 10));
// List resIndextList = Search.binaryAllSearch(arr, 0, arr.length - 1, 6);
// System.out.println(resIndextList);
System.out.println(Search.insertSearch(arr, 0, arr.length - 1, 9));
}
}
/**
* 查找：顺序查找，二分查找/折半查找，插值查找，斐波那契查找/黄金分割点查找
*/
class Search {
/**
* 1,线性查找,不找到全部，找到一个就返回。
*
* @param arr
* @return
*/
public static int seqSearch(int[] arr, int value) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) {
return i;
}
}
return -1;
}
/**
* 2-1，二分查找的数组应该是有序的
*
* @param arr
* @param left
* @param right
* @param findValue
* @return
*/
public static int binarySearch(int[] arr, int left, int right, int findValue) {
//递归结束条件1
if (left > right) {
return -1;
}
int mid = (left + right) >> 1;
int midVal = arr[mid];
if (findValue > midVal) { //正序,向右查询
return binarySearch(arr, mid + 1, right, findValue);
} else if (findValue < midVal) {
return binarySearch(arr, left, mid - 1, findValue);
} else {
return mid; //递归结束条件1
}
}
/**
* 2-2,找到所有的值后放入集合中返回
* 1，找到mid索引值，不要马上返回
* 2，向mid索引值的左边扫描，将所有满足条件的下标找到加入集合
* 3，向mid索引值的右边扫描，将所有满足条件的下标找到加入集合
*
* @param arr
* @param left
* @param right
* @param findValue
* @return
*/
public static List<Integer> binaryAllSearch(int[] arr, int left, int right, int findValue) {
//递归结束条件1
if (left > right) {
return new ArrayList<>();
}
int mid = (left + right) >> 1;
int midVal = arr[mid];
if (findValue > midVal) { //正序,向右查询
return binaryAllSearch(arr, mid + 1, right, findValue);
} else if (findValue < midVal) {
return binaryAllSearch(arr, left, mid - 1, findValue);
} else {
List<Integer> resIndexList = new ArrayList<>();
//向左扫描
int temp = mid - 1;
while (true) {
if (temp < 0 || arr[temp] != findValue) {
break;
}
resIndexList.add(temp);
temp--;
}
//先将自身加入
resIndexList.add(mid);
//向右扫描
temp = mid + 1;
while (true) {
if (temp > arr.length - 1 || arr[temp] != findValue) {
break;
}
resIndexList.add(temp);
temp++;
}
return resIndexList; //递归结束条件1
}
}
/**
* 3,插入查找算法
*
* @param arr
* @param left
* @param right
* @param findValue
* @return
*/
public static int insertSearch(int[] arr, int left, int right, int findValue) {
//递归结束条件1
if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) {
return -1;
}
int cot = (right - left) / (arr[right] - arr[left]);
int detaY = findValue - arr[left];
int mid = left + cot * detaY;
int midVal = arr[mid];
if (findValue > midVal) { //正序,向右查询
return binarySearch(arr, mid + 1, right, findValue);
} else if (findValue < midVal) {
return binarySearch(arr, left, mid - 1, findValue);
} else {
return mid;
}
}
}