常见查找算法实现（c++）

1 查找基本概念

查找表：由同一类型的数据元素构成的集合

关键字：数据中某个数据项的值；主关键字唯一表示记录；次关键字不唯一表示记录。

查找：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。不存在则出现“空记录”或“空指针”。

查找表的操作方式：

• 静态查找表：只做查找操作的查找表（可以考虑对主关键字排序后，在应用折半查找）
• 动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或删除元素。（考虑二叉排序树技术）

2 复杂度分析

算法	复杂度
顺序表查找	$O(n)$O(n)
有序表查找	$O()$O()
线性索引查找	$O()$O()
二叉排序树	$O()$O()
平衡二叉树（AVL）	$O()$O()
多路查找树（B树）	$O()$O()
散列表查找	$O()$O()

3 代码实现

3.1 顺序表查找

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

3.1 顺序表查找算法

#include <iostream>
using namespace std;

int sequential_search(int* a, int N, int target)  //int a[];int* a;int a[4];
{	
	int j = -1;
	for (int i = 0; i < N; i++)
	{
		if (a[i] == target)
		{
			j = i;
			return j;
		}
	}
	return j;
}

int main()
{
	int a[100];
	int N;
	int i_target = -1;
	cout << "请输入数组元素个数：" << endl;
	cin >> N;
	cout << "请循环输入"<< N << "个数：" << endl;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}

	cout << "请输入需要查找的数：" << endl;
	int target;
	cin >> target;

	i_target = sequential_search(a, N, target);

	if (i_target == -1)
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << "找到,下表为"<< i_target << endl;
	}
	system("pause");
	system("cls");
	return 0;
}

3.2 顺序表查找优化算法

每次循环都要对i<N进行越界判断
解决办法：设置哨兵

#include <iostream>
using namespace std;

int sequential_search(int* a, int N, int target)
{	
	int j = N;
	while (target != a[j])
	{
		j--;
	}
	return j;
}

int main()
{
	int a[100];
	a[0] = 0;//预留给哨兵
	int N;
	int i_target = -1;
	cout << "请输入数组元素个数：" << endl;
	cin >> N;
	cout << "请循环输入"<< N << "个数：" << endl;
	for (int i = 1; i < N+1; i++)
	{
		cin >> a[i];
	}

	cout << "请输入需要查找的数：" << endl;
	int target;
	cin >> target;

	i_target = sequential_search(a, N, target);

	if (i_target == 0)
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << "找到,下表为"<< i_target-1 << endl;
	}
	system("pause");
	system("cls");
	return 0;
}

3.2 有序表查找

3.2.1 二分查找，其复杂度为$O(log_n)$O(logn​)

使用二分查找前提是需要有序表顺序存储，对于需要频繁执行插入或删除的数据集来说，维护有序的排序会带来不小的工作量。

#include <iostream>
using namespace std;

int binary_search(int* a, int n,int target)
{
	int mid, min, max;
	min = 0;
	max = n - 1;
	while (min < max)
	{
		mid = (min + max) / 2;
		if (target > a[mid])
		{
			min = mid+1;
		}
		else if (target > a[mid])
		{
			max = mid - 1;
		}
		else
		{
			return mid;
		}
	}
	return 0;
}

int main()
{
	int a[100];
	int N;
	int i_target = -1;
	cout << "请输入数组元素个数：" << endl;
	cin >> N;
	cout << "请循环输入" << N << "个数：" << endl;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}

	cout << "请输入需要查找的数：" << endl;
	int target;
	cin >> target;

	i_target = binary_search(a, N, target);

	if (i_target == 0)
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << "找到,下表为" << i_target << endl;
	}

	system("pause");
	return 0;
}

3.2.2 插值查找

mid = min + (max - min) * (target - a[min]) / (a[max] - a[min]);

优点：对于表长更大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。
缺点：极端不均匀的数据，插值查找未必是合适的选择。

3.2.3 斐波那契查找

利用黄金分割原理

mid = min +F(k-1)-1;

平均情况优于折半查找，最差情况低于折半查找。

3.3 线性索引查找

3.4 二叉排序树

3.5 平衡二叉树

3.6 多路查找树

3.7 散列表查找

总结