查找算法合集

一、順序搜索法

由于不知道要查找元素的具體位置，只能一個元素一個元素的去判斷。

平均查找(n+1)/2

1. int find(int array[], int  length, int value)  

2. {  

3.     if(NULL == array || 0 == length)  

4.         return -1;  

5.   

6.     for(int index = 0; index < length; index++){  

7.         if(value == array[index])  

8.             return index;  

9.         }  

10.     return -1;  

11. }  

二、折半查找

對于一個有序數組，我們就可以通過二分查找的方法來提高查找效率。時間復雜度O(lgn)

二分查找有兩種寫法，需要特別注意邊界。

（1）左閉右閉[left,right]

也就是left = 0, right = n-1。這時的判斷條件時left < right。并且當去一邊的時候要mid+1或mid-1

1. int search(int array[], int n, int v)  

2. {  

3.     int left, right, middle;  

4.   

5.     left = 0, right = n - 1;    //左閉右閉  

6.   

7.     while (left <= right){      //循環條件  

8.         middle = (left + right) / 2;  

9.         if (array[middle] > v){  

10.             right = middle - 1; //由于middle不符合，所有要middle-1滿足右閉  

11.         }  

12.         else if (array[middle] < v){  

13.             left = middle + 1;  //同上，滿足左閉  

14.         }  

15.         else{  

16.             return middle;  

17.         }  

18.     }  

19.   

20.     return -1;  

21. }  

（2）左閉右開[left,right)

也就是left = 0,right = n。這時不相等時，有left = mid+1 或 right = mid;

1. int search4(int array[], int n, int v)  

2. {  

3.     int left, right, middle;  

4.   

5.     left = 0, right = n;    //左閉右開  

6.   

7.     while (left < right){   //判斷條件，由于是開，就必須不能相等  

8.         middle = (left + right) / 2;  

9.   

10.         if (array[middle] > v){  

11.             right = middle; //滿足右開  

12.         }  

13.         else if (array[middle] < v){  

14.             left = middle + 1;  //滿足左閉  

15.         }  

16.         else{  

17.             return middle;  

18.         }  

19.     }  

20.   

21.     return -1;  

22. }  

在循環體內,計算中間位置的時候,使用的是這個表達式:

middle = (left + right) / 2;

假如,left與right之和超過了所在類型的表示范圍的話,那么middle就不會得到正確的值.
所以,更穩妥的做法應該是這樣的:

middle = left + (right - left) / 2;

三、搜索二叉樹

上面的查找是建立在連續內存基礎之上的，那么如果是指針類型的數據呢？怎么辦呢？那么就需要引入排序二叉樹了。排序二叉樹的定義很簡單：（1）非葉子節點至少一邊的分支非NULL；（2）葉子節點左右分支都為NULL；（3）每一個節點記錄一個數據，同時左分支的數據都小于右分支的數據。可以看看下面的定義：

1. typedef struct _NODE  

2. {  

3.     int data;  

4.     struct _NODE* left;  

5.     struct _NODE* right;  

6. }NODE;  

1. const NODE* find_data(const NODE* pNode, int data){  

2.     if(NULL == pNode)  

3.         return NULL;  

4.   

5.     if(data == pNode->data)  

6.         return pNode;  

7.     else if(data < pNode->data)  

8.         return find_data(pNode->left, data);  

9.     else  

10.         return find_data(pNode->right, data);          

11. }  

四、哈希表法-----鏈式查找，相同映射的，放在一個鏈表中

我們看到（2）、（3）都是建立在完全排序的基礎之上，那么有沒有建立在折中基礎之上的查找呢？有，那就是哈希表。哈希表的定義如下：1）每個數據按照某種聚類運算歸到某一大類，然后所有數據鏈成一個鏈表；2）所有鏈表的頭指針形成一個指針數組。這種方法因為不需要完整排序，所以在處理中等規模數據的時候很有效。其中節點的定義如下：

1. typedef struct _LINK_NODE  

2. {  

3.     int data;  

4.     struct _LINK_NODE* next;  

5. }LINK_NODE;  

 那么hash表下面的數據怎么查找呢？

1. LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data)  

2. {  

3.     int index = data % mod;  

4.     if(NULL == array[index])  

5.         return NULL;  

6.   

7.     LINK_NODE* pLinkNode = array[index];  

8.     while(pLinkNode){  

9.         if(data == pLinkNode->data)  

10.             return pLinkNode;  

11.         pLinkNode = pLinkNode->next;  

12.     }  

13.   

14.     return pLinkNode;  

15. }  

 hash表因為不需要排序，只進行簡單的歸類，在數據查找的時候特別方便。查找時間的大小取決于mod的大小。mod越小，那么hash查找就越接近于普通查找；那么hash越大呢，那么hash一次查找成功的概率就大大增加。