《数算》常见查找算法

在java中,我们常用的查找算法有四种:

线性查找、二分(折半)查找、插值查找、斐波那契(黄金分割点)查找,线性查找可查找有序数列或无序数列,其他三个查找算法必须是有序数列

1.线性查找

一个个进行比较,时间复杂度较高O(n)

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
import java.util.ArrayList;
import java.util.List;

/**
* 线性查找
*/
public class linearSearch {

/**
* 线性查找单个元素
* @param arr
* @param value
* @return
*/
public static int linear(int []arr,int value){
for (int i = 0; i < arr.length; i++) {
if (value==arr[i]){
return i;
}
}
return -1;
}

/**
* 查找多个
* @param arr
* @param value
* @return
*/
public static List<Integer> linears(int[]arr, int value) {
List<Integer> list = new ArrayList();
for (int i = 0; i < arr.length; i++) {
if (value==arr[i]){
list.add(i);
}

}

return list.size()>0?list:null;
}

}

测试

1
2
3
4
5
6
public static void main(String[] args) {
int arr[] = {1,2,8,6,6,7,64,6,16};
System.out.println(linear(arr,6));
System.out.println(linears(arr,6).toString());

}

输出

3
[3, 4, 7]

2.

2.二分查找

二分查找也叫折半查找,查找的数列必须是有序的。

基本思想:用需要查找的值find先与中间结点的关键字(mid)比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表(比中间小就往左查否则就往右查),这样递归进行,直到查找到或查找结束发现表中没有这样的结点。

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
import java.util.ArrayList;
import java.util.List;

/**
* 二分查找:前提是数组要有序的
*/
public class BinarySearch {


/**
* 返回多个
* @param arr 需要查找的数组
* @param left 左边索引
* @param right 右边索引
* @param find 查找值
* @return
*/
public static List<Integer> binarySearchs(int arr[], int left, int right, int find){
if (left>right) return null;//没找到
int mid = (left+right)/2;//折半
int midValue = arr[mid];
if (find>midValue)//向右查找
return binarySearchs(arr, mid+1, right, find);
else if (find<midValue)//向左查找
return binarySearchs(arr, left , mid-1, find);
else{//中间值找到了
List<Integer> list = new ArrayList<>();
int temp = mid-1;
while (temp>=0&&arr[temp]==find)//向左查找:如果越界或者找不到就停止
list.add(temp--);
list.add(mid);//中间的值
temp = mid+1;
while (temp<=arr.length-1&&arr[temp]==find)//向右查找:如果越界或者找不到就停止
list.add(temp++);
return list;
}
}

/**
* 返回单个
* @param arr
* @param left
* @param right
* @param find
* @return
*/
public static int binarySearch(int arr[],int left,int right,int find){
if (left>right) return -1;//没找到
int mid = (left+right)/2;
int midValue = arr[mid];
if (find>midValue)//向右查找
return binarySearch(arr, mid+1, right, find);
else if (find<midValue)//向左查找
return binarySearch(arr, left , mid-1, find);
else//中间值找到了
return mid;
}
}

测试

1
2
3
4
5
6
public static void main(String[] args) {
int arr[] = {6,8,10,15,18,20,32,122,1662};
System.out.println(binarySearch(arr,0, arr.length-1,1662));
int arr2[] ={6,8,10,15,15,15,15,32,61,1235};
System.out.println(binarySearchs(arr2, 0, arr.length-1, 15).toString());
}
3.插值查找

插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。

具体是将折半查找中的求mid索引的公式 mid = (left+right)/2 改为

mid = left + (right - left) * (find- arr[left]) / (arr[right] - arr[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
public class DiffValueSearch {

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

/**
* 差值查找:对于数据量大,值分布较均匀(1,2,3,4,5,6...100)的查找表来说,采用差值查找,速度较快
* 值分布不均匀(1,68,465,1567,1655,1765...)的情况下(因为公式的原因,找头部第一个和找尾部第一个比较快,根据公式,只需要查找一次),该方法不一定比折半(二分)查找要好
* @param arr
* @param left
* @param right
* @param find
* @return
*/
public static int diffValueSearch(int arr[],int left,int right,int find){
System.out.println("查找");//每查找一次就输出
if (left>right||find<arr[0]||find>arr[arr.length-1]) return -1;//没找到

int mid = left+(right-left)*(find-arr[left])/(arr[right]-arr[left]);//自适应
int midValue = arr[mid];

if (find>midValue)//向右查找
return diffValueSearch(arr, mid+1, right, find);
else if (find<midValue)//向左查找
return diffValueSearch(arr, left , mid-1, find);
else//中间值找到了
return mid;
}
}

测试

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
// int arr[] = new int[100];
// for (int i = 0; i < 100; i++) {
// arr[i] = i+1;
// }
int arr[] = { 5, 6, 7, 8, 9, 10, 11,19, 20, 21, 22, 23, 24, 25,28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 59, 60, 63, 64, 65, 66, 67, 71, 72, 75, 76, 77, 78, 79, 83, 88, 89, 92, 93, 94, 95, 99, 100};
// System.out.println(Arrays.toString(arr));
System.out.println(diffValueSearch(arr, 0, arr.length-1, 59));
}

输出

查找
查找
25

1
2
3
4
5
6
7
public static void main(String[] args) {
int arr[] = new int[100];//[1,2,3,4,5,6...100]
for (int i = 0; i < 100; i++) {
arr[i] = i+1;
}
System.out.println(diffValueSearch(arr, 0, arr.length-1, 59));
}

查找

58

4.斐波那契查找

斐波那契查找也称黄金分割点查找

斐波那契数列

黄金分割比(中外比)是把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。由于按此比例设计的造型十分美丽,因此称为黄金分割比。

斐波那契数列{1,1,2,3,5,8,13,21,34,55,,,,,,},发现斐波那契数列的两个相邻数的比例,无限接近黄金分割值0.618。

斐波那契查找原理

与前两种相似,仅仅改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1

F(k-1)-1:

根据斐波那契数列可以得出f[k] = f[k-1]+f[k-2] (k为下标,第几个)

假设我们把整个要查找的数组的长度等斐波那契数列的值f[k],那么数组最后的下标为f[k]-1

根据上一个公式推导 f[k]-1= (f[k-1]-1)+(f[k-2]-1)+1

我们把数组分为两个部分f[k-1]-1和f[k-2]-1,那么中间位置mid=low+F(k-1)-1

low表示开始查找的下标 一开始是0,如果后面发现要查找的值比mid位置的大的话 low = mid+1,让他往右边查找

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
import java.util.Arrays;

public class FibonacciSearch {
public static int maxSize = 20;//斐波那契数列长度

public static int[] fibnacciList(){//斐波那契数列实现
int [] fib = new int[maxSize];
for (int i = 0; i < maxSize; i++) {
if (i<=1){
fib[i] = 1;
continue;
}
fib[i] = fib[i-1]+fib[i-2];
}
return fib;
}

public static int fibonacciSearch(int arr[],int key){
int low = 0;//最左边索引
int high = arr.length-1;//最右边索引
int [] fib = fibnacciList();//斐波那契数列
int k = 0;//数列下标
while (high>fib[k]-1)//找到相应的斐波那契数列的长度
k++;
//如果数列的值比原有数组长那么就需要扩容
int [] temp = Arrays.copyOf(arr, fib[k]);
for (int i = high+1; i < temp.length; i++) {
temp[i] = temp[high];//让扩容后的值等于最后一位的值
}
while (low<=high){
int mid = low +fib[k-1]-1;
//数组的长度fib[k]-1 = (fib[k-1]-1)+(fib[k-2]-1)+1 fib[k-1]-1等于mid左边的子数组 fib[k-2]-1等于mid右边的数组

if (key<temp[mid]){//左查找
high = mid-1;
k--;
}else if (key>temp[mid]){//右查找
low = mid+1;
k-=2;
}else {//找到了
if (mid <= high)
return mid;
else//如果找到的是超过high,说明是向右查找,并且超过了原有数组的长度,直接返回最后一位数的值
return high;
//return mid;
}

}
return -1;//没找到

}

}

测试

1
2
3
4
5
6
public static void main(String[] args) {
int arr[] = {6,8,10,15,18,20,32,122,132,1662,1760};
System.out.println(fibonacciSearch(arr, 1662));
System.out.println(fibonacciSearch(arr, 10));
System.out.println(fibonacciSearch(arr, 55));
}

输出

9
2
-1