Java中常用的查找有

  • 线性查找
  • 二分查找/折半查找
  • 插值查找
  • 斐波那契查找/黄金分割点查找

都是比较简单的,除了斐波那契查找

以下只给出思路与关键方法,算法的源代码放在了git中,需要的自取

leidl97/algorithm-src

二分查找

思想

必须为有序的,可以正序,也可以倒序

每次切一半,找到返回找不到向左右继续查

先按照给定数据的一半找起,如果目标值比mid大,则向右递归,反之,向左递归。

优化:可以查找重复数据,在找到元素之后,向左右依次进行比较,查找所有相同的元素

需要注意的是边界值问题 left必须为<=而不是<

代码实现

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
private static void search(int[] arr,int left, int right, int act) {
if (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > act) {
search(arr, left, mid, act);
} else if (arr[mid] < act) {
search(arr,mid+1, right, act);
} else {
System.out.println("找到数据");
list.add(arr[mid]);
int i = mid+1;
if (i < arr.length) {
while (arr[i++] == arr[mid]) {
System.out.println("找到数据");
list.add(arr[mid]);
}
}
int j = mid-1;
if (j > 0) {
while (arr[j--] == arr[mid]) {
System.out.println("找到数据");
list.add(arr[mid]);
}
}
System.out.println("找到的数据有"+list.size()+"个");
}
} else {
System.out.println("没有该数据");
}
}

插值查找

与二分查找类似,主要解决二分查找的部分情况下效率不高的问题,比如一个1到10的数组,找最边上的1或者10那么就需要查找很多次

换言之就是找mid的方式改变,因数由1/2变为下面的,我也不知道怎么算出来的

img

那么,key就是你查找的目标值

将二分查找代码的这处替换即可

int mid = left + (right - left) * (act - arr[left]) / (arr[right] - arr[left])

所以说对于比较均匀的查找表来说,采用插值查找速度较快

不均匀的情况下,速度不一定比二分快

斐波那契查找

我愿称之为玄学查找,只是换了一个mid点,还贼难懂,快的话也没有哪一个能确切的说明,有的是说加减比乘除快,我没实际测试过,其实也就是换了个mid查找位置。

这个查找需要花费点时间,其实也就是改变了中间节点mid的位置

斐波那契查找也称为黄金分割法查找,将一条线段分割为两个部分,其中一部分比上全长之比等于另一部分与这部分之比,取其前三数字的近似值为0.618。

中间值不在由中间值或者插值得到,而是处于黄金分割点附近

F = { 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , . . . }

img

难点

1、为什么需要拆分为f(k-1) -1 而不是 f(k-1)?

需要找到黄金分割点,也就是mid点,可以按照此点作为判断的标志,方便进行向前向后进行查找,当然也可以另作定义,不过写起来会比较麻烦

img

花时间的点

2、为什么向前查找是k-1,向后查找是k-2

img

花时间的点

为什么斐波那契查找更有效率?

二分法采用的是除法,而这是加减法

代码实现

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
public class FibonacciSearch {
public static void main(String[] args) {
int[] a = {1,8,10,89,1000,1234};
sort(a,1234);
}
//{1,1,2,3,5,8,13,21}
private static int[] fib() {
int[] fib = new int[20];
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < fib.length; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib;
}

private static int sort(int[] arr, int act) {
int low = 0;
int high = arr.length - 1;
int k = 0;//fib下标k
int mid = 0;//黄金分割点
int[] f = fib();//拿到斐波那契数列
//获取到黄金分割点,数列长度大于数组长度且最接近的数组值
while (high > f[k] - 1) {
k++;
}
//f[k]的值可能大于数组长度,所以需要扩容。原数组的长度要接近斐波那契的值
int[] temp = Arrays.copyOf(arr,f[k]-1);
//将temp为0的位置填充
for (int i = arr.length; i < temp.length; i++) {
temp[i] = arr[high];
}
//循环查找
while (low <= high) {
mid = low + f[k-1] - 1;
if (act < temp[mid]) {
//向左查找
high = mid - 1;
//为什么是k--,全部 = 前面 + 后面,前面有F[K-1]个元素,可以继续拆分为f[k-2] + f[k-3],在f[k-1]的前面继续查找
k--;
} else if(act > temp[mid]){
//向右查找
low = mid + 1;
//为什么是k-2,全部 = 前面 + 后面,后面有f[k-2]个元素,将其拆分,需要在f[k-3]的位置进行查找,原来是k-1,现在是k-3所以要-2
k -= 2;
} else {
//找到,需要进一步判断下标,防止越界
if (mid < high) {
System.out.println("找到元素,下标为:"+mid);
return 0;
} else {
System.out.println("找到元素,下标为:"+high);
return 0;
}
}
}
System.out.println("未找到元素");
return -1;
}
}