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变为下面的，我也不知道怎么算出来的
那么，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 , . . . }
难点
1、为什么需要拆分为f(k-1) -1 而不是 f(k-1)？
需要找到黄金分割点，也就是mid点，可以按照此点作为判断的标志，方便进行向前向后进行查找，当然也可以另作定义，不过写起来会比较麻烦
花时间的点
2、为什么向前查找是k-1，向后查找是k-2
花时间的点
为什么斐波那契查找更有效率？
二分法采用的是除法，而这是加减法
代码实现
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);
}
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;
int mid = 0;
int[] f = fib();
while (high > f[k] - 1) {
k++;
}
int[] temp = Arrays.copyOf(arr,f[k]-1);
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--;
} else if(act > temp[mid]){
low = mid + 1;
k -= 2;
} else {
if (mid < high) {
System.out.println("找到元素,下标为："+mid);
return 0;
} else {
System.out.println("找到元素,下标为："+high);
return 0;
}
}
}
System.out.println("未找到元素");
return -1;
}
}
|
