C++ 查找算法
查找算法查找是在大量的信息中寻找一个特定的元素。
查找算法正式定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
顺序查找算法
顺序查找也称为线形查找，属于无序查找算法。
基本思想
从数据线性结构表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值 k 相比较，若相等则表示查找成功。
若扫描结束仍没有找到关键字为 k 的节点，表示查找失败。
说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表（即数组）。
顺序查找算法举例
顺序找数
输入不重复的 n 个数（n < 1000），找一个指定的数 k。
输入为两行。第一行为数 n 和 k，表示数的个数和指定的数；第二行为 n 个数，以空格隔开。
输出为一行，表示数 k 在 n 个数中的位置；如果没有，则输出 "NO"。
我的程序如下：
// 顺序找数问题
#include <iostream>
using namespace std;
int main()
{
int a, n, k, i;
cin >> n >> k;
for (i = 0; i < n; i++)
cin >> a;
for (i = 0; i < n; i++)
{
if (a == k)
{
cout << i;
return 0;
}
}
cout << "NO";
return 0;
}
二分查找算法
二分查找也称为折半查找，属于有序查找算法。
基本思想
用给定值 k 先与中间节点的关键字比较，中间结点把线性表分成两个子表，若相等则表示查找成功。
若不相等，再根据 k 与该中间结点的关键字比较结果确定下一步查找那个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的节点。
说明：元素必须是有序的，如果是无序的则要先进行排序操作。
二分查找举例
二分找数
输入排好序的不重复的 n 个数，找一个指定的数 k。
输入为两行，第一行为数 n 和 k，表示数的个数和指定的数；第二行为 n 个数，以空格隔开。
输出位一行，表示数 k 在 n 个数中的位置；如果没有，则输出 "NO"。
我的程序如下：
// 利用二分查找算法找数
#include <iostream>
using namespace std;
int main()
{
int a, n, k, i, mid, flag = 0, low = 1, high;
cin >> n >> k;
high = n;
for (i = 0; i < n; i++)
{
cin >> a;
}
for (i = 0; i < n; i++)
{
if (a == k)
{
flag = 1;
break;
}
}
if (!flag)
{
cout << "NO";
return 0;
}
mid = (1 + n) / 2;
while (true)
{
if (a > k)
{
high = mid - 1;
mid /= 2;
}
else if (a < k)
{
low = mid + 1;
mid = high - mid;
}
else
{
cout << mid;
return 0;
}
}
}
递归实现二分查找：
// 递归二分查找
#include <iostream>
using namespace std;
void fun(int *a, int lo, int hi, int k)
{
if (lo > hi)
{
cout << "NO";
return;
}
int mi = (lo + hi) / 2;
if (a == k)
{
cout << mi;
return;
}
else if (a > k)
fun(a, lo, mi - 1, k);
else
fun(a, mi + 1, hi, k);
}
int main()
{
int a = {}, n, k, i, flag = 0, low = 1, high;
cin >> n >> k;
high = n;
for (i = 0; i < n; i++)
{
cin >> a;
}
fun(a, low, high, k);
return 0;
}
查找算法总结
查找算法有很多，这里只介绍了顺序查找和二分查找。
顺序查找就是一个一个排查。
二分查找就是一半一半排查，但是需要保证查找的是一个有序线性表。
二分查找的效率比顺序查找要高，但是其要求比顺序查找要高。
查找算法和枚举算法的相似和区别之处：
查找算法和枚举算法本质上都是搜索算法，二者是一个思路的东西。
但是枚举算法比较原始，要一个一个地去尝试。
查找算法更广泛，包括一些不是求出所有解的尝试。
枚举算法是全范围找解，不一定是找到解就结束。
查找算法是范围内找解，找到了解就可以结束。
页:
[1]