顺序查找和二分查找

一、顺序查找思想

       1、 从表的一端开始扫描,顺序扫描线性表,依次扫描到的结点关键字与给定的值K相比较.如果当前扫描到的结点的关键字与给定的值K相等,则查找成功;若扫描结束后,仍未找到关键字与给定的值K相等,则查找失败;

     2、顺序查找既适用于顺序存储结构,也适用于线性表的链式存储结构;

     3、ASL= (n+1)/2为其平均查找长度

     4、优点：算法简单，对存储结构形式没有要求 缺点：浪费空间，当长度非常大是效率低

     5、算法描述：

/**
*顺序查找
*@param int a[] 表示查找的库
*@param int length 表示数组a的长度
*@param int key 表示需要查找的目标对象
*@return  int
*/
int orderSerch(int a[],int length,int key){
	int count = 0;
	if(key >a[length-1]){
	      cout<<"您输入的元素不存在！"<<endl;
	}
	for(int i = 0; i< length ;){
		if(key >a[i] ){
			count++;
		    i++;    
		}else if(key == a[i]){
			cout<<"顺利查到了，查找成功！"<<endl;
			cout<<"查找次数："<<count<<endl;
			recode[0] = count;
		    return i;
		}else{
			cout<<"没有查找到，查找失败！"<<endl;
			cout<<"查找次数："<<count<<endl;
			return -1;
		}
	}
}

         二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

               折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。这些都是从百度文库copy过来的只是便于理解，由于此算法太简单了，这里就不多说了。

贴上代码：

/**
*二分查找
*@param int a[] 表示查找的库
*@param int length 表示数组a的长度
*@param int key 表示需要查找的目标对象
*@return  int
*/
int BinarySerch(int a[],int length ,int key){
	     int count = 0;
	     if(key >a[length-1]){
	           cout<<"您输入的元素不存在！"<<endl;
			   return -1;
	     }
         int low = 0,high = length-1;//low 和high表示的是顺序表的低位和高位，分别指向顺序表的第一个位置和最后一个位置
		 int mid = 0;//用来记录中间值的
		 while(low <= high ){
			  count++;
		      mid = (low + high )/2;
			  if(a[mid] == key){
				    cout<<"查找次数："<<count<<endl;
					recode[1] = count;
			        cout<<"查找成功！"<<endl;
					return 1;
			  }
			  if(a[mid] < key ){
			        low = mid+1;
			  }
			  if(a[mid] > key ){
			         high = mid-1;
			  }
		 }
		 if(high == mid&& a[mid] != key ){
			   cout<<"查找次数："<<count<<endl;
		       cout<<"查找失败！"<<endl;
			   return -1;
		 }
}

#include<iostream>
#include<stdlib.h>
#include<windows.h>
using namespace std;
int recode[2]={0};
//快速排序以递归实现的代码
void QKSort(int a[],int low,int high)
{
    if(low>=high)
    {
          return;
    }
    int i = low;
    int j = high;
    int  key = a[low];
	while(i != j){
		for(;j != i;j--){
			if(a[j] <= key ){
			     a[i] = a[j];
				 break;
			}
		}
		for(;i != j;i++){
			if(a[i] > key){
			     a[j] = a[i];
				 break;
			
			}
		}
	} 


    a[i]=key;
    QKSort(a,low,i-1);
    QKSort(a,j+1,high);
}
/**
*顺序查找
*@param int a[] 表示查找的库
*@param int length 表示数组a的长度
*@param int key 表示需要查找的目标对象
*@return  int
*/
int orderSerch(int a[],int length,int key){
	int count = 0;
	if(key >a[length-1]){
	      cout<<"您输入的元素不存在！"<<endl;
	}
	for(int i = 0; i< length ;){
		if(key >a[i] ){
			count++;
		    i++;    
		}else if(key == a[i]){
			cout<<"顺利查到了，查找成功！"<<endl;
			cout<<"查找次数："<<count<<endl;
			recode[0] = count;
		    return i;
		}else{
			cout<<"没有查找到，查找失败！"<<endl;
			cout<<"查找次数："<<count<<endl;
			return -1;
		}
	}
}
/**
*二分查找
*@param int a[] 表示查找的库
*@param int length 表示数组a的长度
*@param int key 表示需要查找的目标对象
*@return  int
*/
int BinarySerch(int a[],int length ,int key){
	     int count = 0;
	     if(key >a[length-1]){
	           cout<<"您输入的元素不存在！"<<endl;
			   return -1;
	     }
         int low = 0,high = length-1;//low 和high表示的是顺序表的低位和高位，分别指向顺序表的第一个位置和最后一个位置
		 int mid = 0;//用来记录中间值的
		 while(low <= high ){
			  count++;
		      mid = (low + high )/2;
			  if(a[mid] == key){
				    cout<<"查找次数："<<count<<endl;
					recode[1] = count;
			        cout<<"查找成功！"<<endl;
					return 1;
			  }
			  if(a[mid] < key ){
			        low = mid+1;
			  }
			  if(a[mid] > key ){
			         high = mid-1;
			  }
		 }
		 if(high == mid&& a[mid] != key ){
			   cout<<"查找次数："<<count<<endl;
		       cout<<"查找失败！"<<endl;
			   return -1;
		 }
}
//菜单
void menu(){
        cout<<"               |----------------------------------------------------|"<<endl;
		cout<<"               |----------1、二分查找                ---------------|"<<endl;
		cout<<"               |----------2、顺序查找                ---------------|"<<endl;
		cout<<"               |----------3、查找次数比较            ---------------|"<<endl;
		cout<<"               |----------------------------------------------------|"<<endl;


}
int count1=0;
void operation(int a[],int length){
	  menu();
	  count1++;
	  int key= 0;
	  cout<<"请选择需要的服务："<<endl;
	  int input = 0;
	  cin >>input;
	  if(input <0||input >3){
	       cout<<"请重新选择："<<endl;
		   operation(a,length);
	  }
	  char c=0;
	  cout<<"-----"<<count1<<endl;
	  if(count1 >4){
	        system("CLS");
			operation(a,length);
			count1= 0;
	  }
	  switch(input){
	  case 1:cout<<"进行的是二分查找---"<<endl;cout<<"请输入需查找的元素：";cin>>key;BinarySerch(a,length,key);cout<<"请选择是否继续操作：Y/N"<<endl;cin>>c;
		  if(c =='Y'||c=='y'){operation(a,length);}else if(c=='N'||c=='n'){return ;}else{cout<<"输入选择有误!"<<endl;}
	  case 2:cout<<"进行的是顺序查找---"<<endl;cout<<"请输入需查找的元素：";cin>>key;orderSerch(a,length,key);cout<<"请选择是否继续操作：Y/N"<<endl;cin>>c;
		  if(c =='Y'||c=='y'){operation(a,length);}else if(c=='N'||c=='n'){return ;}else{cout<<"输入选择有误!"<<endl;}
	  case 3:cout<<"查找查找次数："<<endl;cout<<"二分查找查找次数："<<recode[1]<<endl;cout<<"顺序查找查找次数："<<recode[0]<<endl;
		  cout<<"请选择是否继续操作：Y/N"<<endl;cin>>c;
		  if(c =='Y'||c=='y'){operation(a,length);}else if(c=='N'||c=='n'){return ;}else{cout<<"输入选择有误!"<<endl;operation(a,length);}
	  
	  }


}
int main()
{
      int a[33]={2,4,5,1,7,8,0,9,10,11,12,13,14,15,16,17,19,18,6,55,33,44,32,78,76,65,46,99,33,66,77,67,43};
      QKSort(a,0,32);
	  cout<<"库元素："<<endl;
      for(int i=0;i<33;i++)
      {
             cout<<a[i]<<"  ";
      }
	  cout<<endl;
	  operation(a,33);
      system("PAUSE");
      return 0;
}