顺序查找

￡神魔★判官ぃ 2024-04-19 11:29 24阅读 0赞

顺序表的查找分为三种。简单顺序查找、有序表的二分查找、索引表的顺序查找。这里主要介绍前两种。

一、简单顺序查找

简单顺序查找对数据表的特性没有要求，即是否具有递增递减特性基本不影响查找的性能。基本死就

是从表的一段开始逐个比较元素，若找到则返回元素在表中对应位置；否则，则返回一个无意义的位置标

识。

值得一提的是设置监视哨这一思想，将a\[0\]设置成监视哨则可以避免每次比较元素后都需要判断下标是

否越界这一问题，从而节省了时间。当然，a\[0\]中将不能在存放有效元素。

下面介绍一个以整型数组为例的查找实现：

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  /\*直接顺序查找\*/
2.  int sequential\_search(int a\[\],int n,int key) //n为数组元素个数，key为待查找元素 
3.  \{
4.  int i=n;
5.  a\[0\]=key; //a\[0\]是监视哨 
6.  
7.  while(a\[i\]!=key) //若数组中无key，则一定会得到a\[0\]=key 
8.  i--;
9.  
10. return i; //查找失败返回0 
11. \}

/*直接顺序查找*/
    int sequential_search(int a[],int n,int key)  //n为数组元素个数，key为待查找元素
    {
    	int i=n;
    	a[0]=key;   //a[0]是监视哨
    
    	while(a[i]!=key)  //若数组中无key，则一定会得到a[0]=key
    		i--;
    
    	return i;     //查找失败返回0
    }

二、有序表的二分查找

显然二分查找要求表是升序或降序的。并利用有序这一特性改善了查找性能。那么，若原始表无序又

该如何呢？排序呗！

以升序表为例：

二分查找的基本过程如下：设查找变量首尾下标分别用low和high标志，将待查关键字和上述区域的中

间元素比较，中间元素下标为mid=(low+high)/2，并根据比较结果，分别作以下处理，

①key==a\[mid\]，查找成功，返回mid的值；

②key<a\[mid\]，则继续查找，查找区域变成low=low,high=mid-1。

③key>a\[mid\]，也继续查找，查找区域变成low=mid+1,high=high。

现在，又出现了另一个关键问题：查找何时结束？显然，若查找到key了，返回位置即是结束；如果表

中没有key则是当low>high是结束。

1、二分查找的非递归算法：

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  int bin\_search(int a\[\],int n,int key) //n为数组元素个数，key是待查找元素 
2.  \{
3.  int mid,low=0,high=n-1; //默认从数组起始位置开始查找 
4.  
5.  while(low<=high)
6.  \{
7.  mid=(low+high)/2; //折半 
8.  
9.  if(key==a\[mid\]) //根据比较结果划分查找区域 
10. return mid;
11. else if(key<a\[mid\])
12. high=mid-1;
13. else
14. low=mid+1;
15. \}
16. 
17. return \-1; //没有查找到，返回一个不可能的下标作为标志 
18. \}

int bin_search(int a[],int n,int key)  //n为数组元素个数，key是待查找元素
    {
    	int mid,low=0,high=n-1;   //默认从数组起始位置开始查找
    
    	while(low<=high)
    	{
    		mid=(low+high)/2;   //折半
    
    		if(key==a[mid])     //根据比较结果划分查找区域
    			return mid;
    		else if(key<a[mid])
    			high=mid-1;
    		else
    			low=mid+1;
    	}
    
    	return -1;    //没有查找到，返回一个不可能的下标作为标志
    }

2、递归算法：

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  int bin\_search(int a\[\],int low,int high,int key)
2.  \{
3.  int mid;
4.  
5.  if(low>high)
6.  return \-1;
7.  else
8.  \{
9.  mid=(low+high)/2;
10. 
11. if(a\[mid\]==key)
12. return mid;
13. else if(key<a\[mid\])
14. return bin\_search(a,low,mid-1,key);
15. else
16. return bin\_search(a,mid+1,high,key);
17. \}
18. \}

int bin_search(int a[],int low,int high,int key) 
    {
    	int mid;
    
    	if(low>high)
    		return -1;
    	else
    	{
    		mid=(low+high)/2;
    		
    		if(a[mid]==key)
    			return mid;
    		else if(key<a[mid])
    			return bin_search(a,low,mid-1,key);
    		else
    			return bin_search(a,mid+1,high,key);
    	}
    }

写在最后，简单顺序查找的查找长度为O(n)，二分查找的查找长度为O(log2n)。可见，后者比前者具

有更好的性能，但不要忘了数据表可能要排序这一点可能会 带来的性能消耗。

[view plain]: http://blog.csdn.net/lulipeng_cpp/article/details/7521132#