学习笔记：数据结构与算法（十七）：查找算法
- 顺序查找
- 插值查找（按比例查找）
- 斐波那契查找
- 线性索引查找
-
- 稠密索引
- 分块索引
- 倒排索引
查找算法分为静态查找和动态查找。
静态查找：数据集合稳定，不需要添加、删除元素的查找操作
动态查找：数据集合在查找的过程中需要同时添加或删除元素的查找操作
查找结构：
对于静态查找，用线性表结构组织数据，可以使用顺序查找算法，如果对关键字进行排序，可以使用折半查找算法或斐波那契查找算法等提高效率
对于动态查找，可以使用二叉排序树的查找技术，或者散列表结构来解决一些问题。
顺序查找
也叫线性查找，过程为：从第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值进行比较，如果相等，则成功。如果查找了所有的记录还是找不到相等的，那就是查找失败。
实现演示代码
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，定义为黄金比例然后取整。
线性索引查找
稠密索引
应用于数据量不是特别大的。
分块索引
为了减少索引项的个数，有序的进行分块，并且有关键字。注意：块间是有序的，但是块内是无序的（如果块内也是有序需要消耗更大的内存空间）
倒排索引
根据值找记录，而不是根据记录找值。缺点：记录号表不定长。
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: