DS博客作业05查找

0.PTA得分截图

查找题目集总得分，请截图，截图中必须有自己名字。题目至少完成总题数的2/3，否则本次作业最高分5分。没有全部做完扣1分。

1.本周学习总结（0-4分）

1.1 总结查找内容

查找的性能指标ASL

ASL(Average Search Length)，即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度。
用于静态查找表中顺序表的查找,对于含有n个记录的表，查找成功时的平均查找长度为

pi：概率
ci：查找次数

顺序表

顺序查找是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定的值相等，则查找成功，找到所查的记录，如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中无所查的记录，查找失败。n很大时，顺序查找效率很低下。
对于含n个数据的顺序表
ASL(成功)=(1+2+…+n)/n=(n+1)/2
ASL(失败)=(n×n)/n=n

int  Search(int* a, int n, int key)
{
	int i;
	a[0] = key;   /*设a[0]为要查找的值*/
	i = n;        /*从末尾开始查找*/
	while (a[i] != key)
	{
		i--;
	}
	return i;     /*返回0则查找失败*/
}

二分查找

二分查找的前提是线性表中的记录必须是数据有序（通常从小到大有序），线性表必须采用顺序存储。二分查找的方法是：在有序表中，取中间记录作为比较对象，若给定数据与中间记录的数据相等，则查找成功；若给定值小于中间记录的数据，则在中间记录的左半区继续查找，若给定值大于中间记录的数据，则在中间记录的右半区继续查找。不断重复以上过程，直到查找成功，或者所有查找区域无记录，查找失败为止。
ASL(成功)=(log₂n+1)-1

int search(int* a, int n, int key)
{
	int low, high, mid;
	low = 1;
	high = n;
	while (low <= high)
	{
		mid = (low + high) / 2;   /*折半*/
		if (key < a[mid])
			high = mid - 1;       /*最高下标调整到中位下标小一位*/
		else if (key > a[mid])
			low = mid + 1;        /*最低下标调整到中位下标大一位*/
		else
			return mid;           /*查找成功*/
	}
	return 0;
}

二叉搜索树

二叉搜索树具有下列性质：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。