- 一、顺序查找算法
- 1.1、算法介绍
- 1.2、算法实现
- 二、二分查找算法
- 2.1、算法介绍
- 2.2、算法实现
- 2.3、优化
- 三、插值查找算法
- 3.1、算法介绍
- 3.2、算法实现
- 四、斐波那契(黄金分割法)查找算法
- 4.1、简介
- 4.2、算法实现
一、顺序查找算法 1.1、算法介绍
顺序查找(Order Search)也称为线形查找
- 从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值num相比较,若相等则表示查找成功
- 若扫描结束仍没有找到关键字等于num的结点,表示查找失败
- 这种查找方式效率可能并不是最好的,但是确实最容易理解和实现的。
1.2、算法实现
public static int orderSearch(int[] arr, int num) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == num) {
return i;
}
}
return -1;
}
二、二分查找算法 2.1、算法介绍
二分查找(Binary Search)也称折半查找,它是一种效率较高的查找方法,但二分查找要求 线性表必须采用顺序存储结构 ,并且表中元素按关键字有序排列。
- 首先确定该数组的中间下标:mid = (left + right) / 2
- 让 arr[mid] 和要和查找的元素比较,如果要查找的元素更大,说明应该向右查找,反之向左
- 将左(右)边当成一个新数组,重复第一第二步,即进行递归
- 找到了就结束递归,或者遍历完了数组也没找到,也结束递归
2.2、算法实现
public static int binarySearch(int[] arr, int num) {
return binarySearch(arr, 0, arr.length - 1, num);
}
public static int binarySearch(int[] arr, int left, int right, int num) {
int mid = (left + right) / 2;
// 当 left > right 时说明已递归完整个数组,但是没有找到
if (left > right || num < arr[0] || num > arr[arr.length - 1]) {
return -1;
}
// 如果值小于中间值
if (num < arr[mid]) { // 往左边递归找
return binarySearch(arr, left, mid - 1, num);
// 如果值大于中间值
} else if (num > arr[mid]) { // 往右边递归找
return binarySearch(arr, mid + 1, right, num);
} else {
// 找到!!!!
return mid;
}
}
2.3、优化
当一个有序数组中有多个相同的值时,将所有的数值下标都找到:{1, 2, 2, 2, 7, 8, 9}
public static ListbinarySearch(int[] arr, int left, int right, int num) { List list = new ArrayList<>(); int mid = (left + right) / 2; // 当 left > right 时说明已递归完整个数组,但是没有找到 if (left > right || num < arr[0] || num > arr[arr.length - 1]) { list.add(-1); return list; } if (num > arr[mid]) { // 向右递归 return binarySearch(arr, mid + 1, right, num); } else if (num < arr[mid]) { // 向左递归 return binarySearch(arr, left, mid - 1, num); } else { list.add(mid); // 向左边查找是否有相同的值 int leftTemp = mid - 1; while (leftTemp >= 0 && arr[leftTemp] == num) { list.add(leftTemp); leftTemp--; } // 向右边查找是否有相同的值 int rightTemp = mid + 1; while (rightTemp <= arr.length - 1 && arr[rightTemp] == num) { list.add(rightTemp); rightTemp++; } } return list; } // [3,2,1]
三、插值查找算法 3.1、算法介绍
插值查找(Insert Value Search)是二分查找的一种改良
主要是改良了算法计算mid的值
mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left)
- 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找,速度较快
- 关键字分布不均匀的情况下,该方法不一定比二分查找要好。
3.2、算法实现
public static int insertValueSearch(int[] arr, int num) {
return insertValueSearch(arr, 0, arr.length - 1, num);
}
public static int insertValueSearch(int[] arr, int left, int right, int num) {
if (left > right || num < arr[0] || num > arr[arr.length - 1]) {
return -1;
}
int mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left);
if (num < arr[mid]) {
return insertValueSearch(arr, left, mid - 1, num);
} else if (num > arr[mid]) {
return insertValueSearch(arr, mid + 1, right, num);
} else {
return mid;
}
}
四、斐波那契(黄金分割法)查找算法 4.1、简介
斐波那契查找(Fibonacci Search)又叫黄金分割查找,斐波那契查找和二分查找、插值查找也类似,数组也要是有序的。
不同之处还是mid的计算方法,mid不再是中间或者插值得到,而是位于黄金分割点的附近:mid = left + f(k-1) - 1。要使用斐波那契查找,就要先构建一个斐波那契数列,斐波那契数列的长度就和原始数组保持一致即可,主要是用来获取中间索引mid。
- 斐波那契数列: {1,1,2,3,5,8,13,21,34,55} 相邻两个数的比例无限接近为 0.618
- 由斐波那契数列 F[K] = F[k-1] + F[K-2] 的性质,可以得到 F[K]-1 = (F[K-1]-1) + (F[k-2]-1) + 1
- 只要顺序表的长度为 F[K-1],则可以将该表分为长度为 F[K-1]-1 和 F[k-2]-1
- 但顺序表长度 n 不一定为 F[K]-1,所以需要将原来的顺序长度 n 增加至 F[k]-1
4.2、算法实现
// 获取斐波那契数列 {1,1,2,3,5,8,13,21,34,55 ....}
public static int[] fib(int length) {
int[] fibArr = new int[length];
fibArr[0] = 1;
fibArr[1] = 1;
for (int i = 2; i < length; i++) {
fibArr[i] = fibArr[i - 1] + fibArr[i - 2];
}
return fibArr;
}
//斐波那契查找算法
public static int fibonacciSearch(int[] arr, int num) {
int[] f = fib(arr.length); //获取斐波那契的数组
int left = 0; //原始数组左边的下标
int right = arr.length - 1; //原始数组右边的下标
int k = 0; //斐波那契数组的下标
while (f[k] - 1 < right) { //指向数组的最后索引
k++;
}
//由于f(k)不是步长为1的递增数列,所以可能出现f(k) - 1的值大于原始数组最后一个索引的情况
//比如原始数组最大索引为4,那么此时f(k)就等于5,所以要构造一个新数组,不够的部分会用0填充
//如果多余部分用0填充可能会造成查找失败,因此,需要将0的部分填充为原来数组中的最后一个元素
int[] temp = Arrays.copyOf(arr, f[k]);
for (int i = right + 1; i < temp.length; i++) {
temp[i] = arr[right];
}
while (left <= right) { //循环查找
int mid = left + f[k - 1] - 1; //获取mid
if (num < temp[mid]) { //往左查找
right = mid - 1;
k -= 1;
} else if (num > temp[mid]) { //往右查找
left = mid + 1;
k -= 2;
} else {
return mid <= right ? mid : right; //返回下标
}
}
return -1;
}



