一步一步写算法（之查找）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    无论是数据库，还是普通的ERP系统，查找功能数据处理的一个基本功能。数据查找并不复杂，但是如何实现数据又快又好地查找呢？前人在实践中积累的一些方法，值得我们好好学些一下。我们假定查找的数据唯一存在，数组中没有重复的数据存在。

    （1） 普通的数据查找

    设想有一个1M的数据，我们如何在里面找到我们想要的那个数据。此时数据本身没有特征，所以我们需要的那个数据可能出现在数组的各个位置，可能在数据的开头位置，也可能在数据的结束位置。这种性质要求我们必须对数据进行遍历之后才能获取到对应的数据。

view plaincopy to clipboardprint?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; 

} 

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;

}分析：

    由于我们不清楚这个数据判断究竟需要多少次。但是，我们知道，这样一个数据查找最少需要1次，那么最多需要n次，平均下来可以看成是（1+n）/2，差不多是n的一半。我们把这种比较次数和n成正比的算法复杂度记为o（n）。

    （2）上面的数据没有任何特征，这导致我们的数据排列地杂乱无章。试想一下，如果数据排列地非常整齐，那结果会是什么样的呢？就像在生活中，如果平时不注意收拾整齐，那么找东西的时候非常麻烦，效率很低；但是一旦东西放的位置固定下来，所有东西都归类放好，那么结果就不一样了，我们就会形成思维定势，这样查找东西的效率就会非常高。那么，对一个有序的数组，我们应该怎么查找呢？二分法就是最好的方法。

view plaincopy to clipboardprint?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; 

} 

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;

}分析：

    上面我们说到普通的数据查找算法复杂度是o（n）。那么我们可以用上面一样的方法判断一下算法复杂度。这种方法最少是1次，那么最多需要多少次呢？我们发现最多需要log（n+1）/log（2）即可。大家可以找个例子自己算一下，比如说7个数据，我们发现最多3次；如果是15个数据呢，那么最多4次；以此类推，详细的论证方法可以在《算法导论》、《计算机编程艺术》中找到。明显，这种数据查找的效率要比前面的查找方法高很多。

    （3） 上面的查找是建立在连续内存基础之上的，那么如果是指针类型的数据呢？怎么办呢？那么就需要引入排序二叉树了。排序二叉树的定义很简单：（1）非叶子节点至少一遍分支非NULL；（2）叶子节点左右分支都为NULL；（3）每一个节点记录一个数据，同时左分支的数据都小于右分支的数据。可以看看下面的定义：

view plaincopy to clipboardprint?typedef struct _NODE 

{ 

    int data; 

    struct _NODE* left; 

    struct _NODE* right; 

}NODE; 

typedef struct _NODE

{

       int data;

       struct _NODE* left;

       struct _NODE* right;

}NODE;    那么查找呢，那就更简单了。

view plaincopy to clipboardprint?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);         

} 

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）都是建立在完全排序的基础之上，那么有没有建立在折中基础之上的查找呢？有，那就是哈希表。哈希表的定义如下：1）每个数据按照某种聚类运算归到某一大类，然后所有数据链成一个链表；2）所有链表的头指针形成一个指针数组。这种方法因为不需要完整排序，所以在处理中等规模数据的时候很有效。其中节点的定义如下：

view plaincopy to clipboardprint?typedef struct _LINK_NODE 

{ 

    int data; 

    struct _LINK_NODE* next; 

}LINK_NODE; 

typedef struct _LINK_NODE

{

       int data;

       struct _LINK_NODE* next;

}LINK_NODE;

    那么hash表下面的数据怎么查找呢？

view plaincopy to clipboardprint?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; 

} 

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表因为不需要排序，只进行简单的归类，在数据查找的时候特别方便。查找时间的大小取决于mod的大小。mod越小，那么hash查找就越接近于普通查找；那么hash越大呢，那么hash一次查找成功的概率就大大增加。

【预告： 下一篇博客介绍排序的内容】