顺序查找和折半查找

顺序查找的算法思想

顺序查找，又叫“线性查找”，通常用于线性表
算法思想：从头到脚挨个找
顺序查找的实现

typedef struct{		//查找表的数据结构（顺序表）
	ElemType *elem;	//动态数组基址
    int TableLen;	//表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
	int i;
    for(i=0;i<ST.TableLen&&ST.elem[i]!=key;++i);
	//查找成功，则返回元素下标；查找失败，则返回-1
    return i=ST.TableLen?-1:i;
}

顺序查找的实现（哨兵）

typedef struct{		//查找表的数据结构（顺序表）
	ElemType *elem;	//动态数组基址
    int TableLen;	//表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;		//哨兵
	int i;
    for(i=ST.TableLen;ST.elem[i]!=key;--i);//从后往前找
    return i;//查找成功，则返回元素下标；查找失败，则返回0
}

优点：无需判断是否越界，效率更高

顺序查找的优化（对有序表）

用查找判定树分析ASL

一个成功结点的查找长度=自身所在层数
一个失败结点的查找长度=其父节点所在层数
默认情况下，各种失败情况或成功情况都等概率发生

折半查找

折半查找的算法思想

折半查找，又称“二分查找”，仅适用于有序的顺序表

33>mid，只可能在右边区域

33<mid，只可能在左边区域

33>mid，只可能在右边区域

33==mid 查找成功

12<mid，只可能在左边区域

12<mid，只可能在左边区域

low>high查找失败

typedef struct{		//查找表的数据结构（顺序表）
    ElemType *elem;	//动态数组基址
    int TableLen;	//表的长度
}SSTable;
//折半查找
int Binary_Search(SSTable L,ElemType key){
	int low=0;high=L.TableLen-1;mid;
    while(low<=high){
        mid=(low+high)/2;		//取中间位置
        if(L.elem[mid]==key)
            return mid;			//查找成功则返回所在位置
        else if(L.elem[mid]>key)
            high=mid-1;			//从前半部分继续查找
        else
            low=mid+1;			//从后半部分继续查找
    }
    return -1;					//查找失败，返回-1
}

查找效率分析

ASL成功=(11+23+34+44)/11=3
ASL失败=(34+48)/12=11/3

折半查找判定树的构造

折半查找的判定树一定是平衡二叉树
判定树结点关键字：左<中<右，满足二叉树排序树的定义
折半查找的查找效率

分块查找

分块查找的算法思想

特点：块内无序、块间有序

//索引表
typedef struct{
	ElemType maxValue;
    int low,high;
}Index;
//顺序表存储实际元素
ElemType List[100];

超出分块范围，查找失败
分块查找，又称索引顺序查找，算法过程如下：
1-在索引表中确定待查记录所属的分块（可顺序、可折半）
2-在块内顺序查找
用折半查找索引

若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指分块中查找
原因：最终low左边一定小于目标关键字，high右边一定大于目标关键字。而分块存储的索引表中保存的是各分块的最大关键字

若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指分块中查找
查找效率分析（ASL）