查找的概念

查找表(SearchTable)：相同類型的數據元素(對象)組成的集合，每個元素通常由若干數據項構成。

關鍵字(Key，碼)：數據元素中某個(或幾個)數據項的值，它可以標識一個數據元素。若關鍵字能唯一標識一個數據元素，則關鍵字稱為主關鍵字；將能標識若干個數據元素的關鍵字稱為次關鍵字。

查找/檢索(Searching)：根據給定的K值，在查找表中確定一個關鍵字等於給定值的記錄或數據元素。

◆ 查找表中存在滿足條件的記錄：查找成功；結果：所查到的記錄信息或記錄在查找表中的位置。

◆查找表中不存在滿足條件的記錄：查找失敗。

查找有兩種基本形式：靜態查找和動態查找。

靜態查找(Static Search)：在查找時只對數據元素進行查詢或檢索，查找表稱為靜態查找表。

動態查找(Dynamic Search)：在實施查找的同時，插入查找表中不存在的記錄，或從查找表中刪除已存在的某個記錄，查找表稱為動態查找表。

查找的對象是查找表，采用何種查找方法，首先取決於查找表的組織。查找表是記錄的集合，而集合中的元素之間是一種完全松散的關系，因此，查找表是一種非常靈活的數據結構，可以用多種方式來存儲。

根據存儲結構的不同，查找方法可分為三大類：

① 順序表和鏈表的查找：將給定的K值與查找表中記錄的關鍵字逐個進行比較，找到要查找的記錄；

② 散列表的查找：根據給定的K值直接訪問查找表，從而找到要查找的記錄；

③ 索引查找表的查找：首先根據索引確定待查找記錄所在的塊，然後再從塊中找到要查找的記錄。

查找方法評價指標

查找過程中主要操作是關鍵字的比較，查找過程中關鍵字的平均比較次數(平均查找長度ASL：AverageSearchLength)作為衡量一個查找算法效率高低的標准。ASL定義為：

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8cD4gICAgICAgxuTW0KO6PC9wPgo8cD4gICAgICAgICAgICAgIFBpo7qy6dXStdppuPa8x8K8tcS4xcLKo6yyu8qn0ruw49DUo6zIz86qsunV0sO/uPa8x8K8tcS4xcLKz+C1yKOsvLRQMT1QMj2hrT1Qbj0xL24go7s8L3A+CjxwPiAgICAgICAgICAgICAgQ2mjurLp1dK12mm49rzHwrzQ6NKqvfjQ0LHIvc+1xLTOyv2hozwvcD4KPGJyPgo8cD48YnI+CjwvcD4KPGgxPtK7oaK+ssyssunV0jwvaDE+CjxwPjxicj4KPC9wPgo8aDI+MS7Ls9DysunV0jwvaDI+CjxwPjxicj4KPC9wPgo8cD48L3A+CjxwPjEuMSAgsunV0su8z+s8L3A+CiAgICAgICC007HttcTSu7bLv6rKvNbwuPa9q7zHwry1xLnYvPzX1rrNuPi2qEsmIzIwNTQwO7340NCxyL3Po6zI9MSzuPa8x8K8tcS52Lz819a6zbj4tqhLJiMyMDU0MDvP4LXIo6yy6dXSs8m5pqO7t/HU8qOsyPTJqMPozerV+7j2se2jrMjUyLvDu9PQ1dK1vc/g06a1xLzHwryjrNTysunV0sqnsNyhozxicj4KPHA+PGJyPgo8L3A+CjxwPjEuMiAgyr7A/To8L3A+CjxwPjxicj4KPC9wPgo8cD48aW1nIHNyYz0="http://www.Bkjia.com/uploadfile/Collfiles/20140106/20140106140845243.jpg" alt="\">

1.3 實例代碼:

#include 
#include 

#define N 15

int SearchFun(int a[],int n,int x)
{
    int i,f = -1;
    
    for (i = 0; i

       運行結果:

        





2.  折半查找(Binary Search)




       折半查找又稱為二分查找，是一種效率較高的查找方法。
       前提條件：查找表中的所有記錄是按關鍵字有序(升序或降序) 。
       查找過程中，先確定待查找記錄在表中的范圍，然後逐步縮小范圍(每次將待查記錄所在區間縮小一半)，直到找到或找不到記錄為止。




2.1  查找思想

       用Low、High和Mid表示待查找區間的下界、上界和中間位置指針，初值為Low=1，High=n。
       ⑴   取中間位置Mid：Mid=?(Low+High)/2?；
       ⑵   比較中間位置記錄的關鍵字與給定的K值：
              ① 相等：查找成功；
              ② 大於：待查記錄在區間的前半段，修改上界指針：High=Mid-1，轉⑴；
              ③ 小於：待查記錄在區間的後半段，修改下界指針：Low=Mid+1，轉⑴；
       直到越界(Low>High)，查找失敗。


2.2舉例

       如圖(a)，(b)所示:















2.3 實例代碼:

#include 
#include 

#define N 15

void QuickSort(int *arr,int left,int right)     //快速排序算法
{
    int f,t;
    int rtemp,ltemp;
    
    ltemp = left;
    rtemp = right;
    f = arr[(left + right)/2];                  //確定分界值
    while (ltemp < rtemp)
    {
        while (arr[ltemp] < f)
        {
            ++ltemp;
        }
        
        while (arr[rtemp] > f)
        {
            --rtemp;
        }
        
        if (ltemp <= rtemp)
        {
            t = arr[ltemp];
            arr[ltemp] = arr[rtemp];
            arr[rtemp] = t;
            --rtemp;
            ++ltemp;
        }
    }
    
    if (ltemp == rtemp)
    {
        ltemp++;
    }
    
    if (left < rtemp)
    {
        QuickSort(arr, left, ltemp-1);
    }
    
    if (left < rtemp)
    {
        QuickSort(arr, rtemp+1, right);
    }
    
}

int SearchFun(int a[],int n,int x)              //折半查找
{
    int mid,low,high;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high)/2;
        if (a[mid] == x)
            return mid;
        
        else if(a[mid] > x)
            high = mid -1;
        
        else
            low = mid + 1;
    }
    
    return -1;
}

int main(int argc, const char * argv[])
{
    // std::cout << "Hello, World!\n";
    int x,n,i;
    int shuzu[N];
    
    srand(time(NULL));
    
    printf("折半查找算法演示!\n");
    printf("排序前:\n");
    
    for (i = 0; i

運行結果:

       





二、動態查找



動態查找可參考 

c/c++常用算法 -- 數據結構.









參考書籍:《C/C++常用算法手冊》  《數據結構-清華大學嚴蔚敏》