顺序查找和二分查找
一、顺序查找思想
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<<"您输入的元素不存在！"<
a[i] ){
count++;
i++;
}else if(key == a[i]){
cout<<"顺利查到了，查找成功！"<
二、二分查找基本思想
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到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<<"您输入的元素不存在！"<
key ){
high = mid-1;
}
}
if(high == mid&& a[mid] != key ){
cout<<"查找次数："<
贴上全部代码：这里我把顺序查找和二分查找弄在了一起，很便于观察和学习，而且使用快排来进行排序，对于向我这样的初学者是一个完整的可学习的代码。
#include
#include
#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<<"您输入的元素不存在！"<
a[i] ){ count++; i++; }else if(key == a[i]){ cout<<"顺利查到了，查找成功！"<
a[length-1]){ cout<<"您输入的元素不存在！"<
key ){ high = mid-1; } } if(high == mid&& a[mid] != key ){ cout<<"查找次数："<
>input; if(input <0||input >3){ cout<<"请重新选择："<
4){ system("CLS"); operation(a,length); count1= 0; } switch(input){ case 1:cout<<"进行的是二分查找---"<
>key;BinarySerch(a,length,key);cout<<"请选择是否继续操作：Y/N"<
>c; if(c =='Y'||c=='y'){operation(a,length);}else if(c=='N'||c=='n'){return ;}else{cout<<"输入选择有误!"<
>key;orderSerch(a,length,key);cout<<"请选择是否继续操作：Y/N"<
>c; if(c =='Y'||c=='y'){operation(a,length);}else if(c=='N'||c=='n'){return ;}else{cout<<"输入选择有误!"<
>c; if(c =='Y'||c=='y'){operation(a,length);}else if(c=='N'||c=='n'){return ;}else{cout<<"输入选择有误!"<
代码经验证过！