【查找算法】——順序查找、折半查找、分塊查找（索引查找）

轉載出處：http://www.cnblogs.com/kunhu/p/3634562.html

查找算法

概述：

查找算法：就是在是資料元素集合中檢視是否存在于指定的關鍵字相等的元素。

查找分為兩種：靜态查找和動态查找。

1) 靜态查找：是指在資料元素集合中查找與給定的關鍵字相等的元素。

2) 動态查找：就是指在查找過程中，如果資料元素集合中不存在與給定的關鍵字相等的元素，則将該元素插入到資料元素集合中。

靜态查找主要包括順序表、有序順序表和索引順序表的查找。

1) 順序表的查找，就是指從表的第一個元素與給定關鍵字比較，直到表的最後。

2) 有序順序表的查找，在查找的過程中如果給定的關鍵字大于表的元素，就可以停止查找，說明表中不存在該元素（假設表中的元素按照關鍵字從小到大排列，并且查找從第一個元素開始比較）

3) 索引順序表的查找是為主表建立一個索引，根據索引确定元素所在的範圍，這樣可以有效地提高查找的效率。

動态查找主要包括二叉排序樹、平衡二叉樹、B-樹和B+樹。

這些都是利用二叉樹和樹的特點對資料元素集合進行排序，通過将元素插入到二叉樹或樹中建立二叉樹或樹，然後通過對二叉樹或樹的周遊按照從小到大輸出元素的序列。

散清單是利用散列函數的映射關系直接确定要查找元素的位置，大大減少了與元素的關鍵字的比較次數。

建立散清單的方法主要有直接定址法、平方取中法、折疊法和除留餘數法（最常用）等。

但是會存在沖突，解決沖突的最為常用的方法主要有兩個：開放定址法和鍊位址法。

一.靜态查找

1.順序表的查找——順序查找

順序查找(Sequential Search)又稱為線性查找，是一種最簡單的查找方法。  

        從表的一端開始，向另一端逐個按要查找的值key 與關鍵碼key進行比較，若找到，查找成功，并給出資料元素在表中的位置；若整個表檢測完，仍未找到與關鍵碼相同的key值，則查找失敗，給出失敗資訊。

說白了就是，從頭到尾，一個一個地比，找着相同的就成功，找不到就失敗。很明顯的缺點就是查找效率低。

【适用性】：适用于線性表的順序存儲結構和鍊式存儲結構。

 平均查找長度=（n+1）/2.

【順序查找優缺點】：

缺點:是當n 很大時，平均查找長度較大，效率低；

優點:是對表中資料元素的存儲沒有要求。另外，對于線性連結清單，隻能進行順序查找。

#include<iostream>
using namespace std;

#define MAX 11

typedef int key_type;

typedef struct element
{
	key_type key;   //關鍵字 
}elem;

int seq_search(elem e[], key_type key, int n)
{
	int i = 0;
	while(i < n && e[i].key != key)
	{
		i++;
	}
	
	if(i < n)
		return i;
	else 
		return -1;
}
 
 int main(int argc, char** argv)
 {
 	elem linelist[MAX] = {1,5,9,7,12,11,10,8,6,2,3};
 	int n = 11;
 	int i = 0;
 	key_type key = 8;
 	printf("線性表中的元素為: \n");
 	
 	while(i < n)
 	{
		printf("%d\n",linelist[i].key);
		i++; 
	}	
	
	printf("\n關鍵字[%d]線上性表中的位置下标為[%d]\n", key, seq_search(linelist, key, n));
	
	getchar();
	system("pause");
 }
           

2.有序順序表的查找——折半查找

        在有序表中，取中間元素作為比較對象，若給定值與中間元素的關鍵碼key相等，則查找成功；若給定值小于中間元素的關鍵碼，則在中間元素的左半區繼續查找；若給定值大于中間元素的關鍵碼，則在中間元素的右半區繼續查找。不斷重複上述查找過程，直到查找成功，或所查找的區域無資料元素，查找失敗。

【步驟】

① low=0；high=length-1；                                                          // 設定初始區間

② 當low>high 時，傳回查找失敗資訊                                         // 表空，查找失敗

③ 當low<=high，mid=(low+high)/2;                                           //确定該區間的中點位置

      a. 若key < elem[mid].key，high = mid-1；轉②                    // 查找在左半區進行

      b. 若key > elem[mid].key，low  = mid+1； 轉②                  // 查找在右半區進行

      c. 若key = elem[mid].key，傳回資料元素在表中位置        // 查找成功

有序表按關鍵碼排列如下：

3,  5,  6,  8,  9,  12,  17,  23,  30,  35,  39,  42

在表中查找關鍵碼為9的資料元素：

#include<iostream>
using namespace std;

#define MAX 12

typedef int key_type;

typedef struct element
{
	key_type key;   //關鍵字 
}elem;


int binary_search(elem e[], key_type key, int n)
{
	int low = 0, high = n - 1;
	int mid;
	
	while(low <= high)
	{
		mid = (low + high)/2;
		
		if(e[mid].key == key)
			return mid;
		else if(key < e[mid].key)
			high = mid - 1;
		     else
			low = mid + 1;
	}
	
	return -1; //沒找到 	
}

 
 int main(int argc, char** argv)
 {
 	elem linelist[MAX] = {3,5,6,8,9,12,17,23,30,35,39,42};
 	int n = 12;
 	int i = 0;
 	key_type key = 9;
 	printf("線性表中的元素為: \n");
 	
 	while(i < n)
 	{
		printf("%d\n",linelist[i].key);
		i++; 
	}	
	
	printf("\n關鍵字[%d]線上性表中的位置下标為[%d]\n", key, binary_search(linelist, key, n));
	
	getchar();
	system("pause");
 }
           

折半查找算法的平均查找長度為O(logn)，與順序查找方法相比，折半查找算法的效率高。速度比順序查找快。 但折半查找隻能使用于有序表，需要對n個元素預先進行排序（僅限于順序存儲結構，對于線性連結清單無法進行折半查找）。  

3.分塊查找（索引查找）

分塊查找又稱索引順序查找，是對順序查找的一種改進。分塊查找要求将查找表分成 若幹個子表，并對子表建立索引表，查找表的每一個子表由索引表中的索引項确定。索引項包括兩個字段：關鍵碼字段(存放對應子表中的最大關鍵碼值) ；指針字段(存放指向對 應子表的指針) ，并且要求索引項按關鍵碼字段有序。查找時，先用給定值key 在索引表中 檢測索引項，以确定所要進行的查找在查找表中的查找分塊(由于索引項按關鍵碼字段有序，可用順序查找或折半查找) ，然後，再對該分塊進行順序查找。

如關鍵碼集合為：

                           （8， 20， 13， 17， 40， 42， 45， 32， 49， 58， 50， 52， 67， 79， 78， 80）

按關鍵碼值20，45，58， 80分為四塊建立索引表。

分塊查找的函數分為如下兩步： a）首先确定待查找的結點屬于哪一塊，即查找所在的塊； b）然後，在塊内查找要查的結點。

設表共n個結點，分b塊，s=n/b

(分塊查找索引表)平均查找長度=Log2（n/s+1）+s/2

(順序查找索引表)平均查找長度=(S2+2S+n)/(2S)

#include<iostream>
using namespace std;

#define MAX 16

typedef int key_type;

struct elem
{
	key_type key; //關鍵字 
};

//索引結構 
struct index         
{
	key_type key; //索引值 
	long low;     //起始位置 
	long high;    //終止位置 
};

int index_search(elem e[], key_type key, int n, index idx[], int idx_length)
{
	int low = 0;
	int high = idx_length - 1;
	int mid;
	
	//采用折半查找在索引表裡找到關鍵字所在的塊
	while(low <= high)
	{
		mid = (low + high)/2;
		if(key < idx[mid].key)
			high = mid - 1;
		else if(key > idx[mid].key)
			low = mid + 1;
		     else
			break;
	} 
	
	//采用順序查找的方法從塊中查找關鍵值
	int i = idx[mid].low;
	
	while(i <= idx[mid].high && e[i].key != key)
	{
		i++;
	} 
	
	if(i > idx[mid].high)
		return -1;
	else
		return i;
}


int main(int argc, char** argv)
{
	elem linelist[MAX] = {
		8, 20, 13, 17,
		40, 42, 45, 32,
		49, 58, 50, 52,
		67, 79, 78, 80
	};
	
	int n = sizeof(linelist) / sizeof(elem);
	key_type key = 50;
	
	//建立索引表
	index index_table[4] = {{20,0,3}, {45,4,7}, {58,8,11}, {80,12,15}}; 
	int idx_length = sizeof(index_table) / sizeof(index);
	
	printf("線性表中的元素為：\n");

	int i = 0;
	
	while(i < n) 
	{
		printf("%d\n",linelist[i].key);
		i++;
	}
	
	printf("\n關鍵字[%d]線上性表中的位置下标為[%d]", key, index_search(linelist, key, n, index_table, idx_length));
	
	getchar();
	system("pause");
}