Fork me on GitHub

折半查找

发表于 | 分类于
字数统计: 423 | 阅读时长 ≈ 1

查找

  • 线性结构：顺序查找，折半查找，分块查找

  • 树形结构：二叉搜索树（二叉排序树），AVL平衡二叉树，B树，B+树

  • 散列结构：散列表Hash，性能分析，冲突处理，效率指标–平均查找长度，查找成功，查找失败

线性表顺序查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct List{
    ElemType *elem;
    int table_len;//表长
}SSTable;

int Search_Seq(SSTable st,ElemType key)
{
 
//顺序表st种顺序查找关键字key的元素，并返回元素的表中位置
    st.elem[0]=key;
    for(int i=st.table_len;st.elem[i]!=key;--i)//从后往找
    {        return i;
    }
}

  • 折半查找：二分查找，只用在有序的顺序表

  • 算法思想：首先将给定值key和表中中间位置元素的关键字比较，如果相等，成功，返回元素位置

1
2
3
4
5
6
7
8
9
10
11
12
13
int Binary_Search(SeqList L,ElemType key)
{
    int low=0,mid;
    int high=L.Table_len-1;
    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;
}//时间复杂度为O(logN)

  • 分块查找：索引顺序查找，吸取顺序查找和折半查找的优点，有动态结构，适用于快速查找

  • B树：多路平衡查找树

  • Hash表：一个把查找表中的关键字映射成该关键字对应地址的函数，叫做Hash(key)=Addr。

  • 散列表：根据关键字而直接进行访问的数据结构，也就是，散列表建立了关键字和存储地址之间的一种直接映射关系。