查找算法總結

====================

順序查找算法

1. 算法描述

  順序比較即可。

2. 平均查找長度

  (n+1)/2, 其中n為表長。

3. 算法實作

    省略

4. 優化思想

  根據經驗，目前被查到越多的元素，将來可能被查到的可能性也越大。是以可以考慮，每次查找到一個元素後，将它和直接前驅交換位置。

如果上述的經驗從機率上來講是成立的，則可以加快順序查找的速度。

二分查找算法

  限制：待查表必須是有序的向量(在記憶體中連續存儲)

  首先和數組中點比較，如果等于則傳回，如果小于中點則在左邊區間查找，如果大于中點則在右邊區間查找。

  lg(n+1)

(1) 非遞歸方式

[cpp] 

view

plain

copy

1. static const int ERROR = -1;   
2. template<typename T>  
3. int binary_search(T *array, const int size, const T & key)  
4. {  
5.  if(NULL == array || size < 1)  
6.  {  
7.   cout << "illegal input!" << endl;  
8.   return ERROR;  
9.  }  
10.  int low = 0, high = size - 1;  
11.  int mid_index = 0;  
12.  while(low <= high)  
14.   mid_index = (low+high)/2;  
15.   if(key == array[mid_index])  
16.   {  
17.    return mid_index;  
18.   }    
19.   else if(key > array[mid_index])  
21.    low = mid_index + 1;   
22.   }  
23.   else   
25.    high = mid_index - 1;  
28.  return ERROR;  
29. }  

(2) 遞歸方式

2. int binary_search_iter(T *array, const int low, const int high, const T & key)  
4.  if(low > high)  
6.   return -1;  
8.  int mid_index = (low+high)/2;  
9.  if(key == array[mid_index])  
11.   return mid_index;  
13.  else if(key > array[mid_index])  
15.   return binary_search_iter(array, mid_index+1, high, key);  
17.  else   
19.   return binary_search_iter(array,low, mid_index-1, key);  

分塊查找算法

1. 基本思想

    以增加空間複雜度為代價(存儲每塊中的最大值已經最大值的位置)，為原數組做一個索引(索引本身是遞增有序的)，這樣先查索引，再查塊内位置。如果索引的選擇科學有效，則可以獲得比順序查找快的速度。

2. 算法描述

   抽取各塊中的最大關鍵字及其起始位置構成一個索引表ID[l..b]，即: ID[i](1≤i≤b)中存放第i塊的最大關鍵字及該塊在表R中的起始位置。由于表R是分塊有序的，是以索引表是一個遞增有序表。

   先用二分法查到元素可能所在的塊起始位置，而後在塊内進行順序查找。

3. 平均查找長度

   平均查找長度在順序查找和二分查找之間，并且當結點數為元素數量的平方根時，查找長度最小。

=======================

二叉排序樹上的查找

   由如何改進二分查找的缺陷(插入和删除操作需要移動大量的資料)而得出的一種算法，用二叉排序樹存儲資料，由于二叉樹的插入和删除操作的時間複雜度相對低，而且也支援二分查找，是以在動态資料查找方面優于二分查找。

   二叉樹的特點是中序周遊可以得到遞增的序列。很容易可以得出在二叉排序樹上進行二分排序的遞歸代碼。

    和二叉排序樹的形态有關。在極端情況下，二叉樹隻有單一的左或右分支，則查找長度為(n+1)/2；如果是平衡二叉樹，則查找長度為lgn(樹的層次)。

散列技術下的查找

    将元素的值和其位置直接對應，對應的方法就是散列函數(如平方取中，除餘法等等)；然而再好的散列函數也會引起沖突，則解決沖突的方法是如拉鍊法，線性探測法，二次探測法等等。

原文連結：

http://blog.csdn.net/fstar007/article/details/7230659