数据结构与算法——顺序查找 、折半查找（也称二分查找） 、索引查找_顺序查找和折半查找的算法

一、查找的相关概念

1、关键字

查找过程中,往往是依据数据元素的某个数据项进行查找,这个数据项通常是数据的关键字。
关键字:是数据元素中某个数据项的值,用以标识一个数据元素。
若关键字能标识唯一的一个数据元素,则称谓主关键字。
若关键字能标识若干个数据元素,则称谓次关键字。
例如：张三 2016010002 男 成都 1.75（主关键字是2016010002，次关键字是张三）

2、平均查找长度 ASL

ASL=P₁C₁+P₂C₂+…+P_nC_n
P_i——查找第i个元素的概率
C_i——查找第i个元素需要的比较次数

3、常见的查找算法

• 顺序查找
• 二分查找
• 索引查找
• 哈希查找

二、顺序查找

1、顺序查找基本思想

从表中指定位置（一般为最后一个，第0个位置设为岗哨）的记录开始，沿某个方向将记录的关键字与给定值相比较，若某个记录的关键字和给定值相等，则查找成功；
反之，若找完整个顺序表，都没有与给定关键字值相等的记录，则此顺序表中没有满足查找条件的记录，查找失败。

int seqsearch(DataType R[], KeyType key)
{
	R[0].key=key, i=n;
	while (R[i].key != key) i=i-1;
	return i; 
}
1
2
3
4
5
6

2、 性能分析

（1）空间复杂度： O(1)
（2） 时间复杂度：查找算法的基本运算是给定值与顺序表中记录关键字值的比较。

• 最好情况： O(1)
• 最坏情况： O(n)
• 平均情况： O(n)

3、顺序表上顺序查找的平均查找长度

平均查找长度（ASL）：给定值与关键字比较次数的期望值。
对于具有n个记录的顺序表，查找成功时的平均查找长度为：

Pi——查找第i个记录的概率
Ci——找到第i个记录数据需要比较的次数 ，
对于顺序表，Ci = n-i+1 。

• 等概率情况
  
• 不等概率
  每个元素的查找概率已知
  每个元素的查找概率未知

三、折半查找

1、查找过程

将待查关键字与有序表中间位置的记录进行比较，若相等，查找成功，若小于，则只可能在有序表的前半部分，若大于则只可能在有序表的后半部分，因此，经过一次比较，就将查找范围缩小一半，这样一直进行下去直到找到所需记录或记录不在查找表中。

查找算法的C语言代码：

int BinarySearch(int r[],int low,int high,int key){
/*元素存储在r[low,hight],用折半查找的方法在数组r中找值为key的元素*/
/*查找成功返回该元素的下标，查找失败否返回0*/
	int mid;
	while(low<=high){
		mid=(low+high)/2;
		if(key ==r[mid]) {return mid;} 
		else if( key>r[mid]) low=mid+1;
		else high=mid-1;
		}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

用递归算法

int Binary_rec(int r[],int low,int high,int key){
/*元素存储在r[low,hight],用折半查找的方法在数组r中找值为key的元素*/
/*查找成功返回该元素的下标，查找失败否返回0*/
	int mid;
	if(low<=high){
		mid=(low+high)/2;
		if(key ==r[mid]) {return mid;} 
		else if( key<r[mid]) return Besearch_rec(r,low,mid-1,key);
		else return Besearch_rec(r,mid+1,high,key);
		}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

2、折半查找的性能分析

ASL（成功）=（1+2 * 2+4 * 3+4 * 4）/ 11=3
ASL（失败）=（4 * 3+4 * 8）/ 12=4

注意：

关键码进行比较的次数即为被查找结点在树中的层数，而具有n个结点的判定树的高度为[log₂n]+1，所以折半查找在查找成功时和给定值进行比较的关键码个数至多为[log₂n]+1。
折半查找不成功的过程就是走了一条从根结点到外部结点的路径。

以深度为h的满二叉树为例，即： n=2^h-1 并且查找概率相等，则

当n>50时，可得近似结果

3、折半查找特点

• 折半查找的查找效率高；
• 平均查找性能和最坏性能相当接近；
• 折半查找要求查找表为有序表；
• 并且，折半查找只适用于顺序存储结构。

四、索引查找

1、索引使用方法

先分析数据规律，建立索引。
再根据索引进行快速定位。
在定位的地方进行细致搜索。

2、索引表的构建

(1) 分块：
第R_k 块中所有关键字< R_k+1块中所有关键字，（k=1, 2, …, L-1）。
(2) 建立索引项：
关键字项：记载该块中最大关键字值；
指针项： 记载该块第一个记录在表中位置。
(3) 所有索引项组成索引表。

3、索引表的查找

索引表的查找——查找表的查找

4、索引表的顺序查找算法思想描述

首先根据待查找关键字在索引表当中定位块。定位的方法是：只要
key>索引块i的最大关键值，则i++，定位下一个索引项；直到定位到
索引块，或者把索引项都定位完也没有比key关键字大的索引项。
如果定位到块，则在块内部进行顺序查找。

5、 索引表的顺序查找算法

int IndexSequelSearch(IndexType ls[], DataType s[], int m, KeyType key){
/*索引表为ls[0]-ls[m-1]，顺序表为s*/
	i=0;
	while(i<m && key>ls [i ].key) i++; /*块间查找*/
	if(i==m)return -1; /*查找失败*/
	else{ /*在块内顺序查找*/
		j=ls[ i ].Link;
		while(Key!=s[j].key && j<ls[ i+1 ].Link) j++;
		if(key = = s[j].key)return j; /*查找成功*/
		else return -1; /*查找失败*/ 
		} 
	}
1
2
3
4
5
6
7
8
9
10
11
12

6、索引顺序查找的ASL

ASL=ASL(索引表）+ASL（块内）

7、 索引表的顺序查找性能分析

其中，n为表长，均匀分为b块，每块含有s个记录

五、三种查找算法比较

注：本文来自作者看中国大学MOOC电子科技大学的数据结构与算法做的笔记