线性表查找

【静态查找】

/* 顺序查找 
查找关键字为K的数据
Tb1 为指针，其元素一个为指向数组的头一个是数组长度 */
int SequentialSearch(List Tb1,ElementType K)
{
    //时间复杂性O(n)
    int i;
    Tb1->Element[0]=K;  //建立哨兵，占据在数组的0位置，数组元素从1开始存放
    for(i=Tb1->Length;Tb1->Element[i]!=k;i--);
        return i;
    /* 无哨兵顺序查找 
        int i;

        for(i=Tb1->Length;i>0 && Tb1->Element[i]!=K;i--);
        return i;
    */
}
typedef struct LNode * List;
struct LNode{
    ElementType Element[MAXSIZE];
    int Length;
}
/* 二分查找 
假设n个数据元素的关键字满足有序（比如小到大）
并且是连续存放的数组，那么可以进行二分查找
时间复杂性是O(LogN)
*/
int BinarySearch(List Tbl,Element K)
{
    /* 在表Tbl中查找关键字为Ｋ的元素 */
    int left,right,mid,NotFound=-1;

    left=1; //初始左边界
    right=Tbl->Length; //初始右边界
    while(left<=right)
    {
        mid=(left+right)/2; //计算中间坐标元素
        if(K>Tbl->Element[mid]) right=mid-1; //调整右边界
        else if(K>Tbl->Element[mid]) left=mid+1; //调整左边界
        else return mid; //查找成功，返回数据元素的下标
    }

    return NotFound; //查找不成功，返回-1
}

【二分查找判定树】

查找树.png

【1】判定树上每一个节点需要查找的次数刚好为该节点所在的层数；
【2】查找成功时查找次数不会超过判定树的深度
【3】n个节点的判定树的深度为（取整）[Log2 N]+1
【4】平均成功查找次数ASL=(44+43+2*2+1)/11=3