数据结构--6.3查找算法（静态、动态）（插值查找）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构--6.3查找算法（静态、动态）（插值查找）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

静态查找：数据集合稳定，不需要添加，删除元素的查找操作。

动态查找：数据集合在查找的过程中需要同时添加或删除元素的查找操作。

对于静态查找来说，我们不妨可以用线性表结构组织数据，这样可以使用顺序查找算法，如果我们在对关键字进行排序，则可以使用折半查找算法或斐波那契查找算法来提高查找的效率。

顺序查找又叫线性查找，是最基本的查找技术，他的查找过程是：

从第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；如果查找了所有的记录仍然找不到与给定值相等的关键字，则查找不成功。

对于动态查找来说，我们则可以考虑使用二叉排序树的查找技术，另外我们还可以使用散列表结构来解决一些查找问题。

///简易的查找算法
#include <stdio.h>
//方法1 
int Sq_Search(int *a,int n,int key)
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(a[i] == key)
		{
			return i;
		}
	}
	return 0;
 } 
 
 //方法2 
int Sq_Search(int *a,int n,int key)
{
	int i;
	a[0] = key;
	while(a[i] != key)
	{
		i--;
	}
	return i;
}

一、插值查找（按比例查找）

int bin_search(int str[],int n,int key)
{
	int low,high,mid;
	low = 0;
	high = n-1;
	while(low <= high)
	{
		mid = low + (key-a[low]/a[high] - a[low])*(high - low); //插值查找的唯一不同点 
		if(str[mid] == key)
		{
			return mid;
		}
		if(str[mid] < key)
		{
			low = mid+1;
		}
		if(str[mid] > key)
		{
			high = mid - 1;
		}
	}
	return -1;
 }

二、斐波那契查找算法（黄金比例 0.618：1）

——斐波那契函数（F[k]）

1，1，2，3，5，8，13，21，34，55，89……

（折半查找，选在0.618的位置）文章来源地址https://www.toymoban.com/news/detail-696185.html

到了这里，关于数据结构--6.3查找算法（静态、动态）（插值查找）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！