public static ArrayList<Integer> searchNumber(int[] arr, int number){
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == number) {
list.add(i);
}
}
return list;
}
}
复制代码
2. 二分查找
二分查找又称折半查找。
前提条件：数组中的数据必须是有序的。
如果数据是乱的，必须先排序。
只能确定当前key在数组中是否存在，不能确定其索引值。
核心：每次清除一半的查找范围。
过程：
界说min和max表示当前要查找的范围
界说中心索引mid（min和max中心的索引）
如果key在mid的左边，缩小范围时，min稳定，max等于mid减1
如果key在mid的右边，缩小范围时，max稳定，min等于mid加1
a. 示例
public class Demo3 {
public static void main(String[] args) {
int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
System.out.println(BinarySearch(arr, 127));
}
public static int BinarySearch(int[] arr, int number){
// 定义范围
int min = 0;
int max = arr.length;
while (true) {
if (min > max) {
return -1;
}
// 定义中间索引
int mid = (min + max) / 2;
// 核心代码
if (arr[mid] > number) {
max = mid - 1;
} else if (arr[mid] < number) {
min = mid + 1;
} else if (arr[mid] == number) {
return mid;
}
}
}
}
复制代码
3. 插值查找
插值查找在二分查找的底子上改进。
前提条件：数据尽可能的分布匀称。
核心： m i d = m i n + k e y − a r r [ m i n ] a r r [ m a x ] − a r r [ m i n ] × ( m a x − m i n ) mid = min + \dfrac{key-arr[min]}{arr[max]-arr[min]}\times(max-min) mid=min+arr[max]−arr[min]key−arr[min]×(max−min)
