第七章学习小结

　　本章的主题是查找，顾名思义，就是针对查找运算，讨论应该采用哪种数据结构，使用什么样的方法，并通过对它们的效率进行分析来比较各种查找算法在不同情况下的优势和劣势。在面向一些数据量很大的实时系统时，使用正确的查找方法来提高查找效率就显得尤为重要。

 

　　上图是本章的思维导图。

 

　　顺序查找方法既适用于线性表的顺序存储结构，又适用于线性表的链式存储结构，下面是顺序查找算法：

int SequenceSearch(int a[], int value, int n)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i]==value)
            return i;
    return -1;
}

复杂度分析：　

　　查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
　　当查找不成功时，需要n+1次比较，时间复杂度为O(n);

　　所以，顺序查找的时间复杂度为O(n)。

 

　　折半查找也称为二分查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点，下面是折半查找的算法：

int BinarySearch(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}

复杂度分析：最坏情况下，关键词比较次数为log₂(n+1)，且期望时间复杂度为O(log₂n)