常见查找算法 二分查找 插值查找 斐波那契查找(黄金分割查找)
查找算法
在上边文章总结了常见的排序算法,本文接着上篇内容来介绍总结常见的查找算法。
- 线性查找
- 二分查找
BinarySearch
- 插值查找
- 斐波那契(黄金分割)查询
线性查找
遍历待查找的数列,逐个比较,直到匹配项介绍。
public static int seqSearch(int[] array, int findVal) {
int length = array.length;
for(int i = 0; i < length; i ++) {
if(findVal == array[i]) {
return i;
}
}
return -1;
}
二分查找Binary Search
二分查找也称折半查找,搜索的特点是:每经历一次比较,都是搜索范围缩小一半。
查找思路:
- 从数列的中间开始查找
- 如果中间元素正好匹配,则查找过程结束
- 如果目标元素大于中间元素,则接着从大于中间元素那一半查找
- 如果目标元素小于中间元素,则接着从小于中间元素那一半查找
中值公式:
具体实现代码:
public class BinarySearch {
public static void main(String[] args) {
int [] array = {1, 10, 20, 30, 40, 50, 50, 50, 60, 70, 80, 90};
// 查找匹配的位置
int index = binarySearch(array, 0, array.length - 1, 90);
if(-1 == index) {
System.err.println("没有找到");
} else {
System.out.println("找到该值,位置在:" + index);
}
//查找所有匹配的位置
List<Integer> results = binarySearch2(array, 0, array.length - 1, 50);
if(results.isEmpty()) {
System.err.println("没有找到");
} else {
System.out.println("找到,位置在:" + Arrays.toString(results.toArray()));
}
}
// 二分查找
public static int binarySearch(int[] array, int left, int right, int findValue) {
System.out.printf("查找中...%d~%d\n", left, right);
// 没有找到
if(left > right) {
return -1;
}
int mid = (left + right) / 2;
int midValue = array[mid];
// 中间值大于待查找值,往左边进行查找
if(midValue > findValue) {
return binarySearch(array, left, mid - 1, findValue);
}
// 中间值小于待查找值,往右边进行查找
else if(midValue < findValue) {
return binarySearch(array, mid + 1, right, findValue);
}
// 找到
else {
return mid;
}
}
// 二分查找(获取所有匹配项)
public static List<Integer> binarySearch2(int [] array, int left, int right, int findValue) {
if(left > right) {
return new ArrayList<>();
}
int mid = (left + right) / 2;
int midValue = array[mid];
if(midValue > findValue) {
return binarySearch2(array, left, mid - 1, findValue);
}
else if(midValue < findValue) {
return binarySearch2(array, mid + 1, right, findValue);
}
else {
List<Integer> results = new ArrayList<>();
// 向左查找
int tmp = mid - 1;
while(array[tmp] == findValue) {
results.add(tmp);
tmp--;
}
results.add(mid);
// 向右查找
tmp = mid + 1;
while(array[tmp] == findValue) {
results.add(tmp);
tmp++;
}
return results;
}
}
}
插值查找
插值查找是在二分查找的基础上进行改进,使开始比较的middle
自适应。
其中值计算公式:
该算法代码:
// 插值查找
// mid = low + (high - low) * (key - a[low]) / (a[high] - a[low])
public static int insertValueSearch(int [] array, int low, int high, int key) {
if(low > high) {
return -1;
}
int mid = low + (high - low) * (key - array[low]) / (array[high] - array[low]);
if(array[mid] < key) {
return insertValueSearch(array, mid + 1, high, key);
}
else if(array[mid] > key) {
return insertValueSearch(array, low, mid - 1, key);
}
return mid;
}
插值查找与二分查找对比:
- 对于数据量较大,关键字分布比较均匀的查找列表来说,插值查找速度会比较快。
- 对于关键字分布不均匀的,插值查找不一定比折半查找好。
斐波那契(黄金分割)查找
斐波那契查找原理:
该查找原理与二分查找和插值查找类似,仅仅改变中间节点middle
位置,middle
位置不再是中间或插值得到,而是位于黄金分割点附近,即mid = low + F(k - 1) - 1
(F,斐波那契数列)。
F(k-1)-1
的说明
- 由斐波那契数列
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
的两段,即中间位置为:mid=low+F[k-1]-1
。 - 类似的每个字段也可以用相同的方式进行分割。
- 可能顺序表长度
n
不一定等于F[k]-1
,需要将原来的顺序表长度n
增加至F[k]-1
。(k值只要使得F[k]-1
大于或等于n)。
public class FibonacciSearch {
public static int maxSize = 20;
public static void main(String[] args) {
// System.out.println(Arrays.toString(fibonacci()));
int[] array = {1, 8, 10, 89, 1000, 1234};
int index = fibonacciSearch(array, 1);
if(-1 == index) {
System.err.println("没有找到");
} else {
System.out.println("找到,位置:" + index);
}
}
// 斐波那契数列数组
public static int[] fibonacci() {
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;
}
// 斐波那契查找
public static int fibonacciSearch(int[] array, int key) {
int length = array.length;
int low = 0;
int high = length - 1;
int k = 0; // 斐波那契分割数的索引
int mid = 0;
int[] f = fibonacci();
// 找到有序表元素个数在斐波那契数列中最接近的最大数列值
while(high > (f[k] - 1)) {
k++;
}
// 补齐有序表
int [] tmpArray = Arrays.copyOf(array, f[k]);
for(int i = length; i < tmpArray.length; i++) {
tmpArray[i] = array[high];
}
while(low <= high) {
mid = low + f[k - 1] - 1;
// 查找值小于中值,在小的那一部分继续查找
if(key < tmpArray[mid]) {
high = mid - 1;
k--;
}
// 查找值大于中值,在大的那一部分继续查找
else if(key > tmpArray[mid]) {
low = mid + 1;
k -= 2;
} else {
// 可能存在补齐列表
if(mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
}
您好,我刚刚搭建了一个博客系统,阅读剩余部分 点击无法使用,想请教一下您。
也是用typecho吗?如果是的话,可以直接插入内容:。
或者点击编辑器上面的工具按钮:摘要分割线 , 快捷键是:Ctrl + M。