线性查找、二分查找和插值查找
|字数总计:1.3k|阅读时长:5分钟|阅读量:|
线性查找
介绍
线性查找（Sequential Search）又叫顺序查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| package com.nanzx.search;
public class SeqSearch {
public static void main(String[] args) {
int arr[] = { 1, 9, 11, -1, 34, 89 };
int index = seqSearch(arr, -11);
if (index == -1) {
System.out.println("没有找到。");
} else {
System.out.println("找到，下标为=" + index);
}
}
public static int seqSearch(int[] arr, int value) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) {
return i;
}
}
return -1;
}
}
|
二分查找
介绍
二分查找（Binary Search）技术，又称为折半查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。它的查找过程是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
递归实现代码
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
| package com.nanzx.search;
public class BinarySearch {
public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89, 1000, 1000, 1234 };
int index = binarySearch(arr, 0, arr.length - 1, 11);
if (index == -1) {
System.out.println("没有找到。");
} else {
System.out.println("找到，下标为=" + index);
}
}
public static int binarySearch(int[] arr, int left, int right, int value) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
int midValue = arr[mid];
if (value < midValue) {
return binarySearch(arr, left, mid - 1, value);
} else if (value > midValue) {
return binarySearch(arr, mid + 1, right, value);
} 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
| package com.nanzx.search;
import java.util.ArrayList;
import java.util.List;
public class BinarySearch {
public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89, 1000, 1000, 1234 };
List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);
System.out.println("resIndexList=" + resIndexList);
}
public static List<Integer> binarySearch(int[] arr, int left, int right, int value) {
if (left > right) {
return new ArrayList<Integer>();
}
int mid = (left + right) / 2;
int midValue = arr[mid];
if (value < midValue) {
return binarySearch2(arr, left, mid - 1, value);
} else if (value > midValue) {
return binarySearch2(arr, mid + 1, right, value);
} else {
List<Integer> resIndexlist = new ArrayList<Integer>();
int temp = mid - 1;
while (true) {
if (temp < 0 || arr[temp] != value) {
break;
}
resIndexlist.add(temp);
temp--;
}
resIndexlist.add(mid);
temp = mid + 1;
while (true) {
if (temp > arr.length - 1 || arr[temp] != value) {
break;
}
resIndexlist.add(temp);
temp++;
}
return resIndexlist;
}
}
}
|
非递归实现代码
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
| package com.nanzx.binarysearchnorecursion;
public class BinarySearchNoRecursion {
public static void main(String[] args) {
int[] arr = { 1, 3, 8, 10, 11, 67, 100 };
int index = binarySearch(arr, 100);
System.out.println("index=" + index);
}
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
} else if (arr[mid] < target) {
left = mid + 1;
}
}
return -1;
}
}
|
插值查找
介绍
插值查找算法类似于二分查找，也需要记录是有序的，不同的是插值查找每次从自适应mid处开始查找。
将二分查找求中间记录的mid 索引公式改成：
key：要查找的值；low：第一个记录在数组中的索引值；high：最后一个记录在数组中的索引值
(key-a[low]) / (a[high]-a[low])就是查找值在这个均匀分布的有序序列中的大致位置的系数
对应的代码公式为：
int mid = left + (right - left) * (value - 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
29
30
31
32
| package com.nanzx.search;
public class InsertValueSearch {
public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89, 1000, 1234};
int index = insertValueSearch(arr, 0, arr.length - 1, 10);
System.out.println("index = " + index);
}
public static int insertValueSearch(int[] arr, int left, int right, int value) {
System.out.println("插值查找次数~~");
if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
return -1;
}
int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
int midValue = arr[mid];
if (value > midValue) {
return insertValueSearch(arr, mid + 1, right, value);
} else if (value < midValue) {
return insertValueSearch(arr, left, mid - 1, value);
} else {
return mid;
}
}
}
|
注意事项
- 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找， 速度较快
- 关键字分布不均匀的情况下，该方法不一定比折半查找要好
微信
支付宝