查找算法分为静态查找动态查找

静态查找:数据集合稳定,不需要添加、删除元素的查找操作
动态查找:数据集合在查找的过程中需要同时添加或删除元素的查找操作

查找结构:
对于静态查找,用线性表结构组织数据,可以使用顺序查找算法,如果对关键字进行排序,可以使用折半查找算法或斐波那契查找算法等提高效率
对于动态查找,可以使用二叉排序树的查找技术,或者散列表结构来解决一些问题。

顺序查找

也叫线性查找,过程为:从第一个(或者最后一个)记录开始,逐个进行记录的关键字和给定值进行比较,如果相等,则成功。如果查找了所有的记录还是找不到相等的,那就是查找失败。
实现演示代码

int Sq_Search( int *a, int n,int key)
{
   
     
	int i;
	for(i = 0;i<= n;i++)
	{
   
     
		if(a[i] == key)
			return i;
	}
	return 0;
}

优化算法,提高效率,避免两次判断。

int Sq_Search( int *a, int n,int key)
{
   
     
	int i = n;
	a[0] = key;
	while(a[i] !=key)
	{
   
     
		i--
	}
	return i;
}

插值查找(按比例查找)

参考折半查找法改进的算法

#include <stdio.h>
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;
}

斐波那契查找

斐波那契数列:1,1,2,3,5,8,13,21,34,55,89…
 
改变mid,定义为黄金比例然后取整。

线性索引查找

稠密索引

 
应用于数据量不是特别大的。

分块索引

 
为了减少索引项的个数,有序的进行分块,并且有关键字。注意:块间是有序的,但是块内是无序的(如果块内也是有序需要消耗更大的内存空间)

倒排索引

 
根据值找记录,而不是根据记录找值。缺点:记录号表不定长。