搜索

基本概念

搜索(search)是各种数据结构中的一种常见运算.
搜索是在给定的数据集合中,寻找符合特定条件的数据,用来搜索的这个特定条件称之为键值.
按数据集合所含数据量的大小来分,搜索可分内部搜索和外部搜索.
当数据量较小,可以直接将它载入内存中进行搜索,称这种搜索为内部搜索.
当数据量较大,无法一次将它载入内存进行搜索,
需要使用辅助存储器来分批次处理,称这种搜索为外部搜索 搜索表:由同一类型数据所组成的集合.
关键字:可唯一标识数据的数据项.
搜索:在搜索表查找关键字值与键值相同的数据.
成功搜索:在搜索表查找到关键字值与键值相同的数据.
不成功搜索:在搜索表未查找到关键字值与键值相同的数据.
最大搜索长度:在成功搜索中,关键字值与键值进行比较的最大次数. 
平均搜索长度(average search length):在成功搜索中,关键字值与键值的平均比较次数.
ASL(n) = sum(p(i)c(i))  
n为数据量,p(i)是取第i个数据的概率,c(i)是搜索第i个数据所需的比较次数.

顺序搜索

循序搜索法(linear search)从搜索表的一段开始循序扫描,
依次将搜索表中的结点关键字值和键值进行比较,
若两者相等,则搜索成功;
若扫描结束,还没有找到与键值相等的关键字值,则搜索失败.

#include<iostream>
#include<ctime>
#include<stdlib.h>
using namespace std;
#define n 81
void Create(int *data){for (int i=0;i<n;i++)data[i]=rand()%150+1;
}	 
void Display(int *data){int i,ColNum=0;for(i=0;i<n;i++){cout<<data[i]<<"\t";ColNum++;if(ColNum==9){ColNum=0;cout<<endl;}}cout<<endl;
}void LinearSearch(int *data,int key){int flag=0;for(int i=0;i<n;i++)if(data[i]==key){cout<<"在第"<<i<<"个位置,找到"<<key<<endl;flag=1; }if(flag==0)cout<<"没有找到"<<key<<endl; 
}int main(){int i,key,data[n];srand(time(NULL));//设置随机数发生器种子Create(data);cout<<"搜索数组"<<endl;Display(data);while(1){cout<<"请输入搜索值(1--150),输入-1退出搜索:"<<endl;cin>>key;if(key==-1) break;LinearSearch(data,key); } 
}

C++中随机函数rand()和srand()的用法请参考

二分搜索

二分搜索法(binary search)只使用于搜索数据已被排序的情况.
假设搜索数据是升序的,二分搜索法是将数据分成两等份,
再比较键值与中间值的大小,如果键值小于中间值,
可确定要搜索的数据为前半部分,否则为后半部分.
如此进行下去,直到搜索成功或不成功.

#include<iostream>
#include<ctime>
#include<stdlib.h>
using namespace std;
#define  N  81void Create(int *data,int n){for (int i=0;i<n;i++)data[i]=rand()%150+1;
}	 
void Display(int *data,int n){int i,ColNum=0;for(i=0;i<n;i++){cout<<data[i]<<"\t";ColNum++;if(ColNum==9){ColNum=0;cout<<endl;}}cout<<endl;
}void LinearSearch(int *data,int key,int n){int flag=0;for(int i=0;i<n;i++)if(data[i]==key){cout<<"在第"<<i<<"个位置,找到"<<key<<endl;flag=1; }if(flag==0)cout<<"没有找到"<<key<<endl; 
}//冒泡排序
void Bubble (int *data,int n){int i,j,index;for(i=1;i<n;i++){for(j=n-1;j>i-1;j--){if(data[j]<data[j-1]){index=data[j];data[j]=data[j-1];data[j-1]=index;				}	}//cout<<"第"<<setw(2)<<i<<"趟排序";Display(data,n); }
}void BinarySearch(int *data,int key,int n){  //数组data,键值key,数组长度n int z,mid,y,flag;// 左中右 标识z=0;y=n-1;if(key<data[z]||key>data[y]){cout<<"键值超出界,无法找到"<<endl;return; }flag=0;while(z<=y){mid=(z+y)/2;if(key<data[mid])y=mid-1;else if(key>data[mid])z=mid+1;else{cout<<"在第"<<mid<<"个位置,搜索到"<<key<<endl;flag=1;break; }}if(flag==0)cout<<"没有搜索到"<<endl; 
}int main(){int i,key,data[N];srand(time(NULL));//设置随机数发生器种子Create(data,N);cout<<"搜索数组"<<endl;Bubble(data,N); Display(data,N);while(1){cout<<"请输入搜索值(1--150),输入-1退出搜索:"<<endl;cin>>key;if(key==-1) break;//	LinearSearch(data,key,N); BinarySearch(data,key,N);} 
}