查找算法

顺序查找

int search_seq(int *A,int len,int key){
    A[0] = key;    //"哨兵"
    for(i=len;A[i]!=key;--i);
    return i;
}

A S L_{\text {成功 }}=\sum_{i=1}^{n} P_{i}(n-i+1)=\frac{n+1}{2}
A S L_{\text {无序表失败}}=n+1
A S L_{\text {有序表失败}}=\sum_{j=1}^{n} q_{j}\left(l_{j}-1\right)=\frac{1+2+\cdots+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}

二分查找

版本一:

int bin_search(){
    int low=0;high=L.len-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;
}

版本二:

//二分查找
int vector_bin_search(struct vector v,int e,int lo,int hi)
{
    while (lo<hi) {
        int mi = (lo+hi)>>1;
        
        if(e<*(v.elem+mi)){
            hi = mi;
        }else{
            lo = mi + 1;
        }
    }
    
    return --lo;
}

A S L_{\text {成功 }}=\frac{1}{n} \sum_{i=1}^{n} l_{i}=\frac{1}{n}\left(1 \times 1+2 \times 2+\cdots+h \times 2^{h-1}\right)=\frac{n+1}{n} \log _{2}(n+1)-1 \approx \log _{2}(n+1)-1
A S L_{\text {失败 }}=\left\lceil\log _{2}(n+1)\right\rceil

分块查找

A S L_{\text {索引表顺序查找 }}=L_{\mathrm{I}}+L_{\mathrm{S}}=\frac{b+1}{2}+\frac{s+1}{2}
A S L_{\text {索引表折半查找 }}=L_{\mathrm{I}}+L_{\mathrm{S}}=\left\lceil\log _{2}(b+1)\right\rceil+\frac{s+1}{2}
最理想的块长为s=\sqrt{n}

posted @ 2021-07-20 20:39:14
评论加载中...

发表评论