查找算法概述
在Java中,常用的查找算法有四种:
1、顺序(线性)查找
2、二分查找/折半查找
3、插值查找
4、斐波那契查找
线程查找
线性查找概述
线性查找十分简单。
现在有一个数列,可以是有序的,可以是无序的。
我们从头到尾依次寻找,如果找到了那么提示找到并返回下标。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
public static int seqSearch(int[] arr, int val) {
int index = -1;
for (int i = 0; i < arr.length; i++) { if (arr[i] == val) { return i; } }
return index; }
|
二分查找
线性查找概述
二分查找必须要在一个有序的数组中进行查找
有序的意思是:从大到小,或者从小到大都可以。
二分查找有两种
二分查找的思想
1、确定好数组元素的中间下标:mid = (left + right) / 2
2、让需要查找的数findVal和arr[mid]比较
- 假如findVal > arr[mid],那么说明findVal的下标在mid之后,那么向右边进行递归查找
- 假如findVal < arr[mid],那么说明findVal的下标在mid之前,那么向左边进行递归查找
- 假如findVal == arr[mid],说明查找到了内容
注意点
结束递归的条件
1、找到了对应的值,我们退出递归
2、所有的数据已经遍历完成,但是还没有找到数据,那么结束递归(这种情况也就是left指针 > right指针)
代码实现
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
|
public static int binarySeach(int[] arr, int left, int right, int findVal) {
if (left > right) { return -1; }
int mid = (left + right) / 2; int midVal = arr[mid];
if (findVal > midVal) { return binarySeach(arr, mid + 1, right, findVal); } else if (findVal < midVal) { return binarySeach(arr, left, mid - 1, findVal); } else { return mid; } }
|
需求:当我们的数组中存在多个相同的值时,如何将这多个相同的值都查到,而不是只返回一个
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
|
public static List<Integer> binarySearchUpgrade(int[] arr, int left, int right, int findVal) { if (left > right) { return null; } int mid = (left + right) / 2; int midVal = arr[mid];
if (findVal > midVal) { return binarySearchUpgrade(arr, mid + 1, right, findVal); } else if (findVal < midVal) { return binarySearchUpgrade(arr, left, mid - 1, findVal); }
else { List list = new ArrayList(); list.add(mid); int temp = mid - 1; while (temp >= 0 && arr[temp] == midVal) { list.add(temp--); } temp = mid + 1; while (temp <= arr.length - 1 && arr[temp] == midVal) { list.add(temp++); } Collections.sort(list); return list; } }
|
插值查找
插值查找概述
插值查找是二分查找的一种更进一步的优化方案,与二分查找不同的是:插值查找的中间点mid是自适应的
我们在二分查找的时候,中间的点是*(left + right)/2*得到的
但是假如使用插值查找,那么中间的点是 left + (right - left) x (findVal - arr[left]) / (arr[right] - arr[left])
这个公式也就是拉格朗日插值(注意,数字必须是有序的,才能使用这个公式)
那么其实插值算法最重要的思想就是这个mid的公式,但是这方面确实涉及到了一些数学的知识
还是记忆下:
left:在数组中,就代表0
right:数组的长度-1
findVal:要查找的值
left + (right - left) x (findVal - arr[left]) / (arr[right] - arr[left])
比如现在有一个数组:int[] arr = {1,2,3,4,….,100};
那么假如我们要查询1的下标,那么按照插值查找的公式应当是:0 + (99 - 0) x (1 - 0) / (99 - 0) = 0
一下子就找到了
所以,插值算法最重要的就是它的自适应,在数字有序排列并且数据量十分多时,插值查找的优势巨大
代码实现
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
|
public static int interpolationSearch(int[] arr, int left, int right, int findVal) {
if (left > right) { return -1; }
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]); int midVal = arr[mid];
if (findVal > midVal) { return binarySeach(arr, mid + 1, right, findVal); } if (findVal < midVal) { return binarySeach(arr, left, mid - 1, findVal); }
return mid; }
|
基本上和二分查找差不多,唯一的区别就是mid的计算
斐波那契(黄金分割)查找
斐波那契查找概述
概念介绍
1、黄金分割点
把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比,取其三位数字的近似值为0.618,这个数值就是黄金分割点。
由于按此比例设计的造型十分美丽,因此成为黄金分割,也称为中外比。这是一个神奇的数字,会带来意想不到的效果。
2、斐波那契数列
斐波那契数列是这样的:{1,1,2,3,5,8,13,21,34,55}
其中除了前两位之外,后面的每一个值都是前面两个值相加得到的结果
斐波那契数列到了最后的数值,两个相邻相邻的数值的比值,其实就无限接近于黄金分割点0.618
3、在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2)=1,F(n)=f(n-1)+F(n-2)(n>=2),……
斐波那契查找的原理
我们刚才讲到,在数学中的定义F(1)=1,F(2)=1,F(n)=f(n-1)+F(n-2)(n>=2)
但是我们知道,在Java中数组的下标是以0开始的,所以根据 F(k) = F(k-1) + F(k-2) 得到:
F(k)-1 = (F(k-1)-1) + (F(k-2)-1) + 1,这样所有的下标都减去了1,符合了程序的定义
其实mid在黄金分割段附近,但是注意,它的值不是F(k-1)-1,我们将它定义为low + F(k-1)-1
也就是说,mid = low + F(k-1)-1,其中low为最左端的值
但是现在有一个问题:假如我们的长度不够了怎么办?比如斐波那契需要长度为8的线段,然而我们只有7个或者更少,那么我们采取的解决措施是:使用最后一个的数值去填充到线段的后半部分,如下:
斐波那契查找举例
假如我们现在有一个数组:*int[] arr = {1,2,3,4,5,6,7,8,9,10}*,假如我们要查询9,下面的步骤应当是这样的:
1、因为数组长度为10,但是斐波那契数列中没有10这个数字,所以补充到13
2、阶段2,找到第一个mid节点,然后数值与9比较
3、因为数值比9小,那么向右递归,寻找第二个mid节点
4、同理,向左递归,直到找到最终数值
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
public static int[] fibonacci(int length) {
int[] fibonacciArr = new int[length];
fibonacciArr[0] = 1; fibonacciArr[1] = 1;
for (int i = 2; i < fibonacciArr.length - 1; i++) { fibonacciArr[i] = fibonacciArr[i - 1] + fibonacciArr[i - 2]; }
return fibonacciArr; }
|
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
|
public static int fibonacciSearch(int[] arr, int[] fibonacci, int val) {
int low = 0; int high = arr.length - 1;
int k = 0;
int mid = 0;
while (arr.length > fibonacci[k]) { k++; } int[] temp = Arrays.copyOf(arr, fibonacci[k]); for (int i = arr.length; i < temp.length; i++) { temp[i] = arr[high]; }
while (low <= high) { mid = low + fibonacci[k - 1] - 1;
if (val < temp[mid]) { high = mid - 1;
k--; continue; } if (val > temp[mid]) { low = mid + 1;
k -= 2; continue; }
if (val == temp[mid]) {
return mid < high ? mid : high; } }
return -1; }
|
斐波那契查找的前提是,一个数组应该是一个有序数组