线性表的查找

目录

1.顺序表查找算法

顺序查找的实现

（带哨兵）顺序查找时间效率分析

 顺序查找的特点

2.二分查找（详细见专栏：Acwing基础课）

二分查找的实现

 二分查找的性能分析——判定树

 二分查找特点

3.分块查找

分块查找的实现

 分块查找性能分析

分块查找特点 

 4.插值查找（了解）

5. 斐波那契查找

---

1.顺序表查找算法

顺序查找的实现

 

 

 改进：运用&，for循环后面加上分号

改进：把待查关键字key存入表头（哨兵），从后往前逐个比较，可以免去查找过程中每一步都要检测是否查找完毕，加快速度

当ST.length较大时，此改进能使进行一次查找所需的平均时间几乎减少一半

（带哨兵）顺序查找时间效率分析

 

 

 顺序查找的特点

2.二分查找（详细见专栏：Acwing基础课）

二分查找的实现

 

 普通折半查找

 二分查找的递归算法

 二分查找的性能分析——判定树

 

 

 时间复杂度 O(logn)

 二分查找特点

对线性链表无效的原因是找不到mid 

3.分块查找

分块查找的实现

条件：1.将表分成几块，且表或者有序，或者分块有序；若i<j，则第j块中所有记录的关键字均大于第i块中的最大关键字

           2.建立“索引表”（每个结点含有最大关键字和指向本块第一个结点的指针，且按关键字有序）

 分块查找性能分析

分块查找特点 

 4.插值查找（了解）

5. 斐波那契查找

int Fibonacci_Search(int* a, int n, int key)
{
	int low, high, mid, i, k;
	low = 1;                 //定义最低下标为记录首位
	high = n;                //定义最高下标为记录末位
	k = 0;
	while (n > F[k] - 1)     //计算n位于斐波那契数列的位置
		k++;
	for (i = n; i < F[k] - 1; i++) //将不满的数值补全
		a[i] = a[n];

	while (low <= high)
	{
		mid = low + F[k - 1] - 1;  //计算当前分隔的下标
		if (key < a[mid])          //若查找记录小于当前分隔记录
		{
			high = mid - 1;        //最高下标调整到分割下标mid-1处
			k = k - 1;             //斐波那契数列下标减一位
		}
		else if (key > a[mid])     //若查找记录大于当前分隔记录
		{
			low = mid + 1;         //最低下标调整到分隔下标mid+1处
			k = k - 2;             //斐波那契数列下标减两位
		}
		else
		{
			if (mid <= n)
				return mid;        //若相等则说明mid即为查找到的位置
			else 
				return n;          //若mid>n，说明是补全数值，返回n
		}
	}
	return 0;
}