常见的查找算法

一、顺序查找

说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表

/**
	 *  在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），便是待查找的数据出现在最后一次。 

三 插补查找 
插补查找是一种类似折半查找的查找方法，插补查找是以比例的概念，求出待查找数据的可能位置，然后进行比较，如果该值比待查找的小，表示待查找的值可能出现在该值之前的范围，就这样一直缩小范围来确定最终的目标。  

四 二叉查找树 
二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 

这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。