基本概念

查找

根据给定的值，在查找表中确定一个其关键字等于给定值的数据元素。

关键字

关键字又细分为主关键字和次关键字。若某个关键字可以唯一地识别一个数据元素时，称这个关键字为主关键字，例如学生的学号就具有唯一性；反之，像学生姓名、年龄这类的关键字，由于不具有唯一性，称为次关键字。

静态查找表和动态查找表

在查找表中只做查找操作，而不改动表中数据元素，称此类查找表为静态查找表；反之，在查找表中做查找操作的同时进行插入数据或者删除数据的操作，称此类表为动态查找表。

平均查找长度ASL

线性表的查找

顺序查找

优点： 简单，对逻辑次序无要求，且不同储存结构均可使用。

缺点： ASL长，时间效率低

ASL： (1+2+..+n)/n=（n+1）/2

int Search_Seq(SSTable ST,KeyType key){
	ST.R[0].key=key;//设置监视哨
	for(i=S+T.length;ST.R[i].key!=key;---i);
	return i;
}

二分查找

前提：
只能是数组，不能是链表，并且数组有序
查找次数：
比较次数等于查找成功时位于的树的深度。
即 ⌊log2n⌋+1⌊log2n⌋+1
ASL：
log2(n+1)−1log2(n+1)−1 (n>50)

int search(int nums[], int size, int target) //nums是数组，size是数组的大小，target是需要查找的值
{
    int left = 0;
    int right = size - 1;	// 定义了target在左闭右闭的区间内，[left, right]
    while (left <= right) {	//当left == right时，区间[left, right]仍然有效
        int middle = left + ((right - left) / 2);//等同于 (left + right) / 2，防止溢出
        if (nums[middle] > target) {
            right = middle - 1;	//target在左区间，所以[left, middle - 1]
        } else if (nums[middle] < target) {
            left = middle + 1;	//target在右区间，所以[middle + 1, right]
        } else {	//既不在左边，也不在右边，那就是找到答案了
            return middle;
        }
    }
    //没有找到目标值
    return -1;
}