常見的查找算法

一、順序查找

說明：順序查找適合于存儲結構為順序存儲或鏈接存儲的線性表

/**
	 *  在s[0]-s[n-1]中順序查找關鍵字為Key的記錄 ,查找成功時返回該記錄的下標序號；失敗時返回-1  
	 */
	int SequelSearch(elemtype s[], keytype Key, int n){
		int i;
		i = 0;
		while (i < n && s[i].Key != Key)
			i++;

		if (s[i].Key == Key)
			return i;
		else
			return -1;
	}

二、二分查找

前提:元素必須是有序的，如果是無序的則要先進行排序操作

1.遞歸實現

/**
	 * 在下屆為low，上界為high的數組a中折半查找數據元素x
	 */
	int binarySearch(elemtype a[], elemtype x, int low, int high) {
		int mid;
		if (low > high)
			return -1;
		mid = (low + high) / 2;
		if (x == a[mid])
			return mid;
		if (x < a[mid])
			return (binarySearch(a, x, low, mid - 1));
		else
			return (binarySearch(a, x, mid + 1, high));
	}

2.非遞歸實現

int binarySearch(elemtype a[], keytype key, int n) {
		int low, high, mid;
		low = 0;
		high = n - 1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (a[mid].key == key)
				return mid;
			else if (a[mid].key < key)
				low = mid + 1;
			else
				high = mid - 1;
		}
		return -1;
	}

三、分塊查找

typedef int keytype;

	typedef struct {
		keytype Key;
	}elemtype;

	typedef struct{
		keytype Key;
		int Link;
	}indextype;

	/**
	 * 分塊查找關鍵字為Key的記錄。索引表為ls[0]-ls[m-1],順序表為s，塊長為l
	 */
	int IndexSequelSearch(indextype ls[],elemtypes[],int m,int l,keytype Key){
		int i,j;
		/*在索引表中順序查找*/
		i=0;
		while(i<m&&Key>ls[i].Key)i++;
	
		if(i>=m)
			return -1;
		else{
		    /*在順序表中順序查找*/
		    j=ls[i].Links;
		    while(Key!=s[j].Key&&j-ls[i].Link<l)
		    	j++;
	
		    if(Key==s[j].Key)
		    	return j;
		    else 
		    	return -1; 
		}
	}

四、二叉樹查找

1.二叉樹查找算法

a.非遞歸算法

btree *search(btree *b,int x){
		/*在二叉樹b中查找x的過程*/
		if(b=NULL) 
			return(NULL);
	
		else{
		     if(b->data==x) 
		    	 return(b);
		     if(x<b->data) 
		    	 return(search(b->left));
		     else 
		    	 return(search(b->right));
		} 
	}

b.遞歸算法

bsnodetype *Search(bsnodetype *bt,keytype Key){
		/*在二叉樹bt中查找元素為Key的元素*/
		bsnodetype *p;
		if(bt==NULL) 
			return(bt);

		p=bt;
		while(p->Key!=Key){
		    if(Key<p->Key) 
		    	p=p->Lchild;
		    else 
		    	p=p->Rchild;
		    if(p==NULL)
		    	break;
		}
		return(p);
	}

2.生成二叉樹

a、向一個二叉樹b中插入一個結點s的函數如下：

void insert(b,s){
		btree *b,*s;
		
		if(b==NULL) 
			b=s;
		else if(s->data==b->data) 
		       return();
		else if(s->data<b->data)
		       insert(b->left,s);
		else if(s->data>b->data)
		       insert(b->right,s);
	}

void create(btree *b){
		int x;
		btree 8s;
		b==NULL;
	
		do{
		   scanf("%d",&x);
		   s=(bnode *)malloc(sizeof(bnode));
		   s->data=x;
		   s->left=NULL;
		   s->right=NULL;
		   insert(b,s); 
		}while(x!=-1);
	}

bsnodetype *Delete(bsnodetype *bt,keytype Key){/*在bt為根結點的二叉樹中刪除值為Key的結點*/
		
		bsnodetype *p,*q;
		if(bt->Key==Key){
		    /*bt的左右子樹均為空*/
		    if(bt->Lchild==NULL&&bt->Rchild==NULL){
		       free(bt); /*刪除葉結點*/
		       return(NULL);
		    }else if(bt->Lchild==NULL){ /*bt的左子樹為空*/
		       p=bt->Rchild;
		       free(bt);
		       return(p);
		    }else if(bt->Rchild==NULL){/*bt的右子樹為空*/
		       p=bt->Lchild;
		       free(bt);
		       return(p); 
		    }else{
		       p=q=bt->Rchild;
		       while(p->Lchild!=NULL)
		    	   p=p->Lchild;
		       p->Lchild=bt->Lchild;
		       free(bt);
		       return(q);
		    }
		}
	
		/*在bt->Lchild為根結點的二叉樹中刪除值為Key的結點*/
		if(bt->Key>Key&&bt->Lchild!=NULL)
		   bt->Lchild=Delete(bt->Lchild,Key);
	
		/*在bt->Rchild為根結點的二叉樹中刪除值為Key的結點*/
		if(bt->Key<Key&&bt->Rchild!=NULL)
		   bt->Rchild=Delete(bt->Rchild,Key);
	
		return(bt);
	}

總結：

一 線性查找 
又稱順序查找，是從數組的第一個元素開始查找，直到找到待查找元素的位置，直到查找到結果。 
最佳的狀況時間是1 ，就是第一個就是待查找的遠射，最差的查找狀況是O（n），就是最后一個是待查找的元素。 

二 折半查找 
折半查找是將待查找的數組元素不斷的分為兩部分，每次淘汰二分之一，但是有個大前提是，元素必須是有序的，如果是無序的則要先進行排序操作，這種查找的方法，類似于找英文字典的Java，我們可以一下子找到字母J開頭的，再仔細找。 
最佳的狀況時間是1，就是第一次分開就查找到了，最差的查找狀態是O（n），便是待查找的數據出現在最后一次。 

三 插補查找 
插補查找是一種類似折半查找的查找方法，插補查找是以比例的概念，求出待查找數據的可能位置，然后進行比較，如果該值比待查找的小，表示待查找的值可能出現在該值之前的范圍，就這樣一直縮小范圍來確定最終的目標。  

四 二叉查找樹 
二叉查找樹是先對待查找的數據進行生成樹，確保樹的左分支的值小于右分支的值，然后在就行和每個節點的父節點比較大小，查找最適合的范圍。 

這個算法的查找效率很高，但是如果使用這種查找方法要首先創建樹。