【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：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一次查找成功的概率就大大增加。
【預告： 下一篇博客介紹排序的內容】
