查找算法

2019-11-06 07:17:27

字体：大中小

来源：转载

供稿：网友

查找，作为应用最为广泛和最基础的算法思想之一，几乎在所有应用程序之中都有它的思想身影。往细一点说：查找可以有顺序查找、二分查找、散列表查找，下面依次来看一下这三种查找思想：

首先，顺序查找，这个思想最为简单，从头到尾按顺序找，笨方法但是很好实现，对于数据量较小的时候还是不错的下面给出一个范例代码（可能有点多余）：

#include <iostream>using namespace std;const int N = 510;int a[N];int main() { int n, x, res = -1; cin >> n; for(int i = 0; i < n; i++) { cin >> a[i]; } while(cin >> x) { res = -1; // 按顺序查找数字所在位置，这里是找数字第一次出现的位置 for(int i = 0; i < n; i++) { if(a[i] == x) { res = i; break; } } cout << "位置：" << res << endl; } return 0;}

看看结果：

这里写图片描述

这里 -1 代表数组中不存在要查找这个数。顺序查找的时间复杂度为 O(n)。

下面来看看看二分查找，二分查找适用于排序之后的数组，算法的思想也很简单：首先对数组进行排序，每次用数组中的中间那个数字和要查找的数字相比较，如果数组中间的那个数字大于要查找的那个数字，那么在数组的左半边继续执行二分查找，否则在数组的右半边继续执行二分查找，直到找到了那个数字为止。文字看得腻？下面我们举个例子：假设我们要在： 4 2 3 1 4 这 5 个数字中查找 2 这个数字，过程如下：

1、先对数组进行从小到大排序：1 2 3 4 4

2、比较 2 和数组中间的数字 3 的大小，明显，2 小于 3，于是在数组的左半边继续二分查找。

3、在 1 2 3 这三个数字中查找数字 2 ，这一次很幸运，中间的那个数字就是 2 ，那么数字 2 就被找到了。

代码：

#include <iostream>#include <algorithm>using namespace std;const int N = 510;int a[N];int binarySearch(int left, int right, int x) { int mid; // 当左边界小于右边界的时候继续查找 if(left >= right) return -1; mid = (left + right) / 2; if(a[mid] == x) return mid; else if(a[mid] > x) return binarySearch(left, mid, x); else // 这里的左边界为 mid+1，因为 mid 所在位置的元素已经被比较过了 return binarySearch(mid+1, right, x); }int main() { int n, x; cin >> n; for(int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); // 调用 C++ 标准库（STL）中的排序算法 while(cin >> x) { cout << "位置：" << binarySearch(0, n, x) << endl; } return 0;}

这里我们写的是递归版的代码，其实我们也可以写成循环版的代码，而且循环版的代码速度会更快：

int binarySearch(int left, int right, int x) { int mid; while(left < right) { mid = (left+right) / 2; if(a[mid] == x) { return mid; } else if(a[mid] > x) { right = mid; } else { left = mid + 1; } } return -1;}int main() { int n, x; cin >> n; for(int i = 0; i < n; i++) { cin >> a[i]; } sort(a, a + n); // 调用 C++ 标准库（STL）中的排序算法 while(cin >> x) { cout << "位置：" << binarySearch(0, n, x) << endl; } return 0;}

看看结果：这里写图片描述

我们可以看到，二分查找找到的位置是排序之后的，如果要输出排序之前的位置，还需要别的手段。因为每次都选择中间的数字比较，二分查找的时间复杂度为 O(logn)，

接下来介绍一种“标记”思想的查找：我们对每次出现的数字都用一个标记数组做一个“标记”，表示这个数字出现过，那么当我们查找的时候，我们直接去看一下标记数组中有没有这个“标记”就行了，下面来看看代码：

#include <iostream>#include <cstring>using namespace std;const int N = 1000010;int a[N];int book[N]; // 标记数组 int main() { int n, x; cin >> n; memset(book, -1, sizeof(book)); // 将标记数组全部置为 -1 for(int i = 0; i < n; i++) { cin >> a[i]; book[a[i]] = i; // 记录数字 a[i] 出现的最后一次位置 } while(cin >> x) { cout << "位置：" << book[x] << endl; } return 0;}

我们可以看到，book 数组中储存的是每一个数字出现的最后一个位置，即为将出现的数字做一个“位置标记”，下面是结果：

这里写图片描述

通过这种思想实现的查找时间复杂度可以降到 O(1) （当然，在忽略输入数据占用时间复杂度的情况下），但是空间复杂度比较大，我们下面要介绍的散列查找也是基于这种思想，当然，这种算法思想也有弊端：输入的数字不能过大，不能超过数组下标能达到的最大的临界值（稍微思考一下就能理解），但是在某些场合这种思想还是挺有用的。

最后来看一下散列查找，上面提到过，散列查找是基于标记数组的思想，而且通过散列查找我们不仅能够对整形数字进行查找，还能够对一些非整形数字的数据类型（字符串、浮点数）进行查找。

其实散列查找的思想就是采用标记数组的思想，只不过当我们碰到一些非整数的数据类型的数据时，我们要将它们转换成整形，那么就拿字符串来说，我们要将字符串转换成为能够作为数组下标的整数，那么可能有些小伙伴要问了，如果我输入一个长度为几万甚至几亿的字符串，哪有那么大的数组下标储存啊！对于这个问题，我们可以通过取余来解决：我们限定一个数组的最大下标值，然后把所有算得到的整数值取余这个最大下标就行了。还有一个问题：对于一个下标只能储存一个值，如果出现了两个字符串转换出来的数组下标相同的情况怎么办呢，我们可以采用移位来处理，将冲突的那个字符串转换的数组下标的整形值通过变换数值来避免冲突，进而储存，下面给出代码：

#include <iostream>#include <cstring>using namespace std;const int N = 1046527;const int MAX_LEN = 14;char save[N][MAX_LEN];int book[N]; // 标记字符串位置的数组 int sum; // 统计储存的字符串总数 int getInt(char ch) { return ch - 'A' + 1;}long long getKey(char str[], int len) { long long sum = 0; for(int i = 0; i < len; i++) { sum += i*(getInt(str[i])); } return sum;} int find(char str[], int len) { long long key = getKey(str, len); int index; for(int i = 0; ; i++) { /* * 获取数组下标冲突的时候数组下标的移位值 , * 在数组下标移位的时候， * 我们要让移位的数值和数组下标的最大值互质， * 这样才能使得移位成功（因为要进行取余运算） */ index = ((key % N) + i*(1+key%(N-1))) % N; if(strcmp(save[index], str) == 0) { return book[index]; // 如果存在返回位置 } else if(strlen(save[index]) == 0) { return -1; // 不存在返回 -1 } } return 0;}int insert(char str[], int len) { long long key = getKey(str, len); int index; for(int i = 0; ; i++) { index = ((key % N) + i*(1+key%(N-1))) % N; if(strcmp(save[index], str) == 0) { // 字符串已经存在就不用插入了 return 0; } else if(strlen(save[index]) == 0) { strcpy(save[index], str); book[index] = sum++; // 储存的字符串总数加 1，并且记录位置（从 0 开始） return 1; } } return 0;}int main() { int n, len; char op[MAX_LEN] = {0}, s[MAX_LEN] = {0}; cin >> n; for(int i = 0; i < n; i++) { memset(s, 0, sizeof(s)); len = strlen(s); cin >> op >> s; if(op[0] == 'i') { insert(s, len); } else { cout << "位置：" << find(s, len) << endl; } } return 0;}

来看看结果：

这里写图片描述