第七章 查找技术

查找的基本概念

关键码：可以表示一个记录的某个数据项；若能唯一标识，称为主关键码，否则为次关键码。 查找：在具有相同类型的记录构成的集合中找出给定条件的记录。 静态查找和动态查找的区别：是否涉及到插入和删除操作。 查找算法的性能：通过平均查找长度ASL进行衡量。

查找结构有：

1.线性表

顺序查找、折半查找、折半查找的递归算法实现，通过插入排序使得数组有序（设置哨兵）

对于表中每个记录的查找过程，可以用折半查找的判定树来描述： 1.从根节点到该节点的路径、给定值的比较次数都等于该记录节点在树中的层数。 2.比较次数最多为log2(n)+1

#include 

using namespace std;
const int N=1e4+5;
int a[N];
class Lin_search
{
public:
    Lin_search(int a[],int n);          //线性表的初始化
    ~Lin_search() {}                    //静态数组，析构函数可为空
    int Seq_search(int k);            //顺序查找
    void Insert_sort();
    int Bin_search1(int k);           //折半查找
    int Bin_search2(int l,int r,int k);           //折半的递归写法
    void display()
    {
        for(int i=1;i