一、线性查找
package work.rexhao.search;
public class SeqSearch {
public static void main(String[] args) {
int[] num = new int[]{
12, 32, 45, 69, 83, 64, 23, 65, 10};
System.out.println(seqSearch(num, 83));
System.out.println(seqSearch(num, 99));
}
private static int seqSearch(int[] num, int i) {
for (int j = 0; j < num.length; j++) {
if (num[j] == i) {
return j;
}
}
return -1;
}
}
二、二分查找
1、思路
- 确定该数组的中间的下标：mid = (left +right) / 2
- 然后让需要查找的数findVal和 arr[mid] 比较：
- findVal > arr[mid]，说明你要查找的数在mid 的右边，因此需要递归的向右查找
- findVal < arr[mid]，说明你要查找的数在mid 的左边，因此需要递归的向左查找
- findval == arr[mid]，说明找到，就返回
- 什么时候我们需要结束递归？
- 找到就结束递归
- 递归完整个数组，仍然没有找到findVal，也需要结束递归（当left>right就要退出）
2、代码实现
package work.rexhao.search;
import java.util.Arrays;
/**
* 二分查找
*
* @author 王铭颢
* @Date 2022/7/3 22:54
*/
public class BinarySearch {
public static void main(String[] args) {
int[] num = new int[]{
10, 12, 23, 32, 45, 64, 65, 69, 83};
System.out.println(Arrays.toString(num));
System.out.println(binarySearch(num, 69, 0, num.length - 1));
System.out.println(binarySearch(num, 99, 0, num.length - 1));
}
public static int binarySearch(int[] num, int target, int left, int right) {
if (left > right) {
return -1;
}
if (num[(left + right) / 2] == target) {
return (left + right) / 2;
} else if (num[(left + right) / 2] > target) {
return binarySearch(num, target, left, (left + right) / 2);
} else {
return binarySearch(num, target, (left + right) / 2 + 1, right);
}
}
}
三、差值查找
1、思路
插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。
自适应mid算法：int mid = left + (right - left) * (target - num[left]) / (num[right] - num[left]);
对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快.
关键字分布不均匀的情况下，该方法不一定比折半查找要好
2、代码实现
package work.rexhao.search;
import java.util.Arrays;
/**
* 差值查找
*
* @author 王铭颢
* @Date 2022/7/4 10:54
*/
public class InsertValueSearch {
public static void main(String[] args) {
int[] num = new int[]{
10, 12, 23, 32, 45, 64, 65, 69, 83};
System.out.println(Arrays.toString(num));
System.out.println(insertValueSearch(num, 69, 0, num.length - 1));
System.out.println(insertValueSearch(num, 99, 0, num.length - 1));
}
private static int insertValueSearch(int[] num, int target, int left, int right) {
int mid = left + (right - left) * (target - num[left]) / (num[right] - num[left]);
if (left > right || mid >= num.length || mid < 0) {
return -1;
}
if (num[mid] == target) {
return mid;
} else if (num[mid] > target) {
return insertValueSearch(num, target, left, mid);
} else {
return insertValueSearch(num, target, mid + 1, right);
}
}
}
四、斐波那契查找
1、思路
mid 位于黄金分割点附近，即 mid-low+F(k-1)-1（F 代表斐波那契数列）
由斐波那契数列 F[k]=F[K-1]+F[k-2]的性质，可以得到 (F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1
(F[k-1]-1)：左边的子序列
(F[k-2]-1)：右边子序列
1：mid
每一子段也用相同的方式分割
顺序表长度n不一定刚好等于 F[k]-1，所以需要将原来的顺序表长度n增加至 F[k]-1
（为了保证数组有序，copyOf会在末尾生成0，用最后一位数来填充后面的0）
2、代码实现
package work.rexhao.search;
import java.util.Arrays;
/**
* 斐波那契查找Demo
*
* @author 王铭颢
* @Date 2022/7/4 22:36
*/
public class FibonacciSearch {
public static void main(String[] args) {
int[] num = new int[]{
10, 12, 23, 32, 45, 64, 65, 69, 83};
System.out.println(Arrays.toString(num));
System.out.println(fibSearch(num, 69));
System.out.println(fibSearch(num, 99));
}
/**
* 生成斐波那契数列
*
* @param maxSize 元素最大个数
* @return 斐波那契数组
*/
public static int[] fib(int maxSize) {
int[] f = new int[maxSize];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < maxSize; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
/**
* 斐波那契查找
*
* @return 索引值
*/
public static int fibSearch(int[] num, int target) {
// 一、生成斐波那契数列
int[] f = fib(20);
// k:斐波那契分隔值的下表
int k = 0;
// 二、扩充数列
// 1.找到适合的fib[k]大小
while (num.length - 1 > f[k]) k++;
// 2.扩充并复制数组
int[] temp = Arrays.copyOf(num, f[k]);
// 3.为了保证数组有序，copyOf会在末尾生成0，用最后一位数来填充后面的0
for (int i = num.length; i < temp.length; i++) {
temp[i] = num[num.length - 1];
}
// 三、查找
int mid = 0;
int low = 0;
int high = num.length - 1;
while (low < high) {
mid = low + f[k - 1] - 1;
if (target > temp[mid]) {
// 比中间大 --> 找右边
low = mid + 1;
k -= 2;
} else if (target < temp[mid]) {
// 比中间小 --> 找左边
high = mid - 1;
k -= 1;
} else {
// 找到了
return mid;
}
}
// 没找到
return -1;
}
}
