二分查找的平均查找长度_二分查找（折半查找）代码实现

整理不易，手有余香请点赞！

---

折半查找，也称二分查找，在某些情况下相比于顺序查找，使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。

在折半查找之前对查找表按照所查的关键字进行排序的意思是：若查找表中存储的数据元素含有多个关键字时，使用哪种关键字做折半查找，就需要提前以该关键字对所有数据进行排序。

代码

完整实现代码

struct SSNode{
    int* elem;
    int length;
}

int SearchBin(SSNode* S, int key){
    int low = 0;
    int high = S->length - 1;
    int mid;

    while(low<high){
        mid = (low + high) / 2;
        if(S->elem[mid] == key)
            return mid;
        if(S->elem[mid] > key)
            high = mid - 1;
        else
            low = mid + 1;

    return -1;
    }
}

int main(int argc, const char * argv[]) {
    // xx
    // ...

    return 0;
}

总结

通过比较折半查找的平均查找长度，同前面介绍的顺序查找相对比，明显折半查找的效率要高。但是折半查找算法只适用于有序表，同时仅限于查找表用顺序存储结构表示。

当查找表使用链式存储结构表示时，折半查找算法无法有效地进行比较操作（排序和查找操作的实现都异常繁琐）。

参考

二分查找（折半查找）算法详解（C语言实现）​c.biancheng.net