查找算法分类
静态查找和动态查找；
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
无序查找和有序查找。
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列。
顺序查找
设计理念
顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
时间复杂度
顺序查找的时间复杂度为O(n)。
java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public class SequentialSearch {
private int[] array;
public SequentialSearch(int[] array) {
this.array = array;
}
public int search(int key) {
for(int i = 0; i < array.length; i++) {
if(array[i] == key) {
return i;
}
}
return -1;
}
}
|
二分查找
元素必须是有序的，如果是无序的则要先进行排序操作。
设计理念
也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
复杂度分析
最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；
java 实现
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
80
81
82
83
84
85
86
87
88
89
|
public class BinarySearch {
private int[] array;
public BinarySearch(int[] array) {
this.array = array;
}
public int searchRecursion(int target) {
if(array == null) {
return -1;
}
return searchRecursion(target, 0, array.length - 1);
}
public int search(int target) {
if(array == null) {
return -1;
}
int start = 0;
int end = array.length - 1;
while(start <= end) {
int mid = start + (end - start) / 2;
if(array[mid] == target) {
return mid;
}else if(target < array[mid]) {
end = mid - 1;
}else {
start = mid + 1;
}
}
return -1;
}
private int searchRecursion(int target, int start, int end) {
if(start > end) {
return -1;
}
int mid = start + (end - start) / 2;
if(array[mid] == target) {
return mid;
}else if(array[mid] < target) {
return searchRecursion(target, mid + 1, end);
}else {
return searchRecursion(target, start, mid -1);
}
}
}
public class BinaryInsertSort {
private int[] array;
public BinaryInsertSort(int[] array) {
this.array = array;
}
public void sort() {
int length = array.length;
for(int i = 1; i < length; i++) {
int temp = array[i];
int insertIndex = binarySearch(i - 1, temp);
if(insertIndex != i) {
for(int j = i; j > insertIndex; j--) {
array[j] = array[j - 1];
}
array[insertIndex] = temp;
}
}
}
public void print() {
for(int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
private int binarySearch(int end, int target) {
int start = 0;
int mid = -1;
while(start <= end) {
mid = start + (end - start) / 2;
if(array[mid] > target) {
end = mid - 1;
}else {
start = mid + 1;
}
}
return start;
}
}
|
插值查找
设计理念
基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
复杂度分析
查找成功或者失败的时间复杂度均为O(log2(log2n))。
java实现
1
2
3
4
5
6
7
8
9
10
11
|
int InsertionSearch(int a[], int value, int low, int high)
{
int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
if(a[mid]==value)
return mid;
if(a[mid]>value)
return InsertionSearch(a, value, low, mid-1);
if(a[mid]<value)
return InsertionSearch(a, value, mid+1, high);
}
|
杨氏矩阵的的查找
设计理念
杨氏矩阵就是行列递增的矩阵。
杨氏矩阵的操作
插入。插入一个数，需要移动其他元素
删除。给定 x,y 坐标，删除那个数，伴随其他元素移动，怎样移动操作最少？
查找 t 是否存在于矩阵中。这也是这篇博客里所要关注的。
返回第 k 大的数。涉及到堆查找，后续博客再细说。
关于查找 t 是否存在于矩阵，书中给了几种实现的方法：
递归实现和非递归实现
优化：
每次不都从每行的第一个数开始查找，左右上下进行比较然后查找。
分治法。杨氏矩阵行列是递增的，那么对角线也是递增的，可以利用对角线划分的区域来缩小要查找数的范围。（实现略）
定位查找法。先定位到第一行最右的数，然后只需要往下走，往左走两种操作即可，相比方法 2 省掉了往右走。
java 实现
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| public class YoungSearch {
private int[][] array;
public YoungSearch(int[][] array) {
this.array = array;
}
public boolean recursionSearch(int x, int y, int target) {
if(x == array.length || y == array[0].length) {
return false;
}
if(target < array[x][y]) {
return false;
}
if(target == array[x][y]) {
System.out.println(String.format("x: %d, y: %d", x, y));
return true;
}
return recursionSearch(x + 1, y, target) || recursionSearch(x, y + 1, target);
}
public boolean search(int target) {
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array[0].length && target >= array[i][j]; j++) {
if(target == array[i][j]) {
System.out.println(String.format("x: %d y: %d", i, j));
return true;
}
}
}
return false;
}
public boolean search2(int target) {
int width = array[0].length;
int height = array.length;
if(target >= array[0][0]) {
int i = 0;
for(; i < width && target >= array[0][i]; i++) {
if(target == array[0][i]) {
System.out.println(String.format("x: %d, y: %d", 0, i));
return true;
}
}
if(i > width - 1) {
i--;
}
for(int j = 1; j < height; j++) {
if(target == array[j][i]) {
System.out.println(String.format("x: %d, y: %d", j, i));
return true;
}else if(target < array[j][i]) {
for(; i >= 0; i--) {
if(target == array[j][i]) {
System.out.println(String.format("x: %d, y: %d", j, i));
return true;
}else if(target > array[j][i]) {
break;
}
}
if(i < 0) {
i++;
}
}else if(target > array[j][i]) {
for(; i < width; i++) {
if(target == array[j][i]){
System.out.println(String.format("x: %d, y: %d", j, i));
return true;
}else if(target < array[j][i]) {
break;
}
}
if(i > width - 1) {
i--;
}
}
}
}
return false;
}
public boolean search3(int target) {
int i = 0;
int j = array[0].length - 1;
int temp = array[i][j];
while(true) {
if(target == temp) {
System.out.println(String.format("x: %d, y: %d", i, j));
return true;
}else if(j > 0 && target < temp){
temp = array[i][--j];
}else if(i < array.length - 1 && target > temp) {
temp = array[++i][j];
}else {
return false;
}
}
}
}
|
分块查找
设计理念
对于待查找的数据列表来说，如果元素变动很少，那么可以先进行排序再查找。但如果这个数据经常需要添加元素，那么每次查找前都需要排序，这并不是一个好的选择。
就有了分块查找，这个概念再学数据库的时候听过。分块查找里有索引表和分块这两个概念。索引表就是帮助分块查找的一个分块依据，就是一个数组，用来存储每块最大的存储值（范围上限）；分块就是通过索引表把数据分为几块。
原理
当需要增加一个元素的时候，先根据索引表，获取这个元素应该在那一块，然后直接把元素加入到相应的块里，而块内的元素直接不需要有序。
从上面可知，分块查找只需要索引表有序，每一个块里的元素可以是无序的，但第 i 块的每个元素一定比第 i-1 块的每一个元素大（小）。当索引表很大的时候，可以对索引表进行二分查找，锁定块的位置，然后对块内的元素进行顺序查找。总性能不如二分查找，但强过顺序查找，更好的是不需要数列完全有序。
举个例子，比如索引表为【10，20，30】,分块一【2，1，4，2】分块二【19，15，18，】分块三【22，27，23】，现在要增加 22 这个数，直接根据索引表把 22 放到分块三最后就行了【22,27,23,22】。
可以看出，分块查找同时有顺序查找和二分查找的有点————不需要有序、速度快。
应用场景
视频网站对用户观看行为记录，每个用户分别观看了一个视频多久，如果对每条这样的记录都放到一个表里，那太多了，可以根据具体业务做分表，一天一个表，表名如 t_user_watch_xxx_20180806，存储查询的时候就可以根据时间去做一个表的分块，在查询详细的记录。
java 实现
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
|
import java.util.ArrayList;
public class BlockSearch {
private int[] index;
private ArrayList<ArrayList<Integer>> list;
public BlockSearch(int[] index) {
this.index = index;
list = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < index.length; i++) {
list.add(new ArrayList<Integer>());
}
}
public void insert(Integer value) {
int i = binarySearch(value);
list.get(i).add(value);
}
public boolean search(int data) {
int i = binarySearch(data);
for(int j = 0; j < list.get(i).size(); j++) {
if(data == list.get(i).get(j)) {
return true;
}
}
return false;
}
public void printAll() {
for(int i = 0; i < list.size(); i++) {
ArrayList<Integer> l = list.get(i);
System.out.println("ArrayList: " + i + ":");
for(int j = 0; j < l.size(); j++) {
System.out.println(l.get(j));
}
}
}
private int binarySearch(int target) {
int start = 0;
int end = index.length - 1 ;
int mid = -1;
while(start <= end) {
mid = (start + end) / 2;
if(target == index[mid]) {
return mid;
}else if(target < index[mid]) {
end = mid - 1;
}else {
start = mid + 1;
}
}
return start;
}
}
|
