無論是數(shù)據(jù)庫，還是普通的ERP系統(tǒng)，查找功能數(shù)據(jù)處理的一個(gè)基本功能。數(shù)據(jù)查找并不復(fù)雜，但是如何實(shí)現(xiàn)數(shù)據(jù)又快又好地查找呢？前人在實(shí)踐中積累的一些方法，值得我們好好學(xué)些一下。我們假定查找的數(shù)據(jù)唯一存在，數(shù)組中沒有重復(fù)的數(shù)據(jù)存在。

（1） 普通的數(shù)據(jù)查找

設(shè)想有一個(gè)1M的數(shù)據(jù)，我們?nèi)绾卧诶锩嬲业轿覀兿胍哪莻€(gè)數(shù)據(jù)。此時(shí)數(shù)據(jù)本身沒有特征，所以我們需要的那個(gè)數(shù)據(jù)可能出現(xiàn)在數(shù)組的各個(gè)位置，可能在數(shù)據(jù)的開頭位置，也可能在數(shù)據(jù)的結(jié)束位置。這種性質(zhì)要求我們必須對(duì)數(shù)據(jù)進(jìn)行遍歷之后才能獲取到對(duì)應(yīng)的數(shù)據(jù)。

int find(int array[], int  length, int value)
{
    if(NULL == array || 0 == length)
        return -1;

    for(int index = 0; index < length; index++){
        if(value == array[index])
            return index;
        }
    return -1;
}

分析：

由于我們不清楚這個(gè)數(shù)據(jù)判斷究竟需要多少次。但是，我們知道，這樣一個(gè)數(shù)據(jù)查找最少需要1次，那么最多需要n次，平均下來可以看成是（1+n）/2，差不多是n的一半。我們把這種比較次數(shù)和n成正比的算法復(fù)雜度記為o（n）。

（2）上面的數(shù)據(jù)沒有任何特征，這導(dǎo)致我們的數(shù)據(jù)排列地雜亂無章。試想一下，如果數(shù)據(jù)排列地非常整齊，那結(jié)果會(huì)是什么樣的呢？就像在生活中，如果平時(shí)不注意收拾整齊，那么找東西的時(shí)候非常麻煩，效率很低；但是一旦東西放的位置固定下來，所有東西都?xì)w類放好，那么結(jié)果就不一樣了，我們就會(huì)形成思維定勢(shì)，這樣查找東西的效率就會(huì)非常高。那么，對(duì)一個(gè)有序的數(shù)組，我們應(yīng)該怎么查找呢？二分法就是最好的方法。

int binary_sort(int array[], int length, int value)
{
    if(NULL == array || 0 == length)
        return -1;

    int start = 0;
    int end = length -1;

    while(start <= end){

        int middle = start + ((end - start) >> 1);
        if(value == array[middle])
            return middle;
        else if(value > array[middle]){
            start = middle + 1;
        }else{
            end = middle -1;
        }
    }

    return -1;
}

分析：

上面我們說到普通的數(shù)據(jù)查找算法復(fù)雜度是o（n）。那么我們可以用上面一樣的方法判斷一下算法復(fù)雜度。這種方法最少是1次，那么最多需要多少次呢？我們發(fā)現(xiàn)最多需要log（n+1）/log（2）即可。大家可以找個(gè)例子自己算一下，比如說7個(gè)數(shù)據(jù)，我們發(fā)現(xiàn)最多3次；如果是15個(gè)數(shù)據(jù)呢，那么最多4次；以此類推，詳細(xì)的論證方法可以在《算法導(dǎo)論》、《計(jì)算機(jī)編程藝術(shù)》中找到。明顯，這種數(shù)據(jù)查找的效率要比前面的查找方法高很多。

（3） 上面的查找是建立在連續(xù)內(nèi)存基礎(chǔ)之上的，那么如果是指針類型的數(shù)據(jù)呢？怎么辦呢？那么就需要引入排序二叉樹了。排序二叉樹的定義很簡(jiǎn)單：（1）非葉子節(jié)點(diǎn)至少一邊的分支非NULL；（2）葉子節(jié)點(diǎn)左右分支都為NULL；（3）每一個(gè)節(jié)點(diǎn)記錄一個(gè)數(shù)據(jù)，同時(shí)左分支的數(shù)據(jù)都小于右分支的數(shù)據(jù)?？梢钥纯聪旅娴亩x：

typedef struct _NODE
{
    int data;
    struct _NODE* left;
    struct _NODE* right;
}NODE;

那么查找呢，那就更簡(jiǎn)單了。

const NODE* find_data(const NODE* pNode, int data){
    if(NULL == pNode)
        return NULL;

    if(data == pNode->data)
        return pNode;
    else if(data < pNode->data)
        return find_data(pNode->left, data);
    else
        return find_data(pNode->right, data);
}

（4）同樣，我們看到（2）、（3）都是建立在完全排序的基礎(chǔ)之上，那么有沒有建立在折中基礎(chǔ)之上的查找呢？有，那就是哈希表。哈希表的定義如下：1）每個(gè)數(shù)據(jù)按照某種聚類運(yùn)算歸到某一大類，然后所有數(shù)據(jù)鏈成一個(gè)鏈表；2）所有鏈表的頭指針形成一個(gè)指針數(shù)組。這種方法因?yàn)椴恍枰暾判?，所以在處理中等?guī)模數(shù)據(jù)的時(shí)候很有效。其中節(jié)點(diǎn)的定義如下：

typedef struct _LINK_NODE
{
    int data;
    struct _LINK_NODE* next;
}LINK_NODE;

那么hash表下面的數(shù)據(jù)怎么查找呢？

LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data)
{
    int index = data % mod;
    if(NULL == array[index])
        return NULL;

    LINK_NODE* pLinkNode = array[index];
    while(pLinkNode){
        if(data == pLinkNode->data)
            return pLinkNode;
        pLinkNode = pLinkNode->next;
    }

    return pLinkNode;
}

分析：

hash表因?yàn)椴恍枰判?，只進(jìn)行簡(jiǎn)單的歸類，在數(shù)據(jù)查找的時(shí)候特別方便。查找時(shí)間的大小取決于mod的大小。mod越小，那么hash查找就越接近于普通查找；那么hash越大呢，那么hash一次查找成功的概率就大大增加。