1>算法思想：
折半查找（Binary Search）的查找过程是：先确定等查记录所在范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。
2>算法
3>算法实现
#include<iostream>
using namespace std;
#define ARRAY_SIZE 11
/*
description:
在标准输出设备上显示数组元素。
parameter：
int* p:指向整形数组首元素的指针
int length:整形数据长度
*/
void myshow(int* p_start,int length){
for(int i=0;i<length;i++){
cout<<"["<<i<<"]:"<<*(p_start+i)<<endl;
}
cout<<endl;
}
/*
返回与关键字key相等的数据元素下标,若不存在，返回-1
@param
int *p_start:首元素地址
int length:列表长度
int key :要查找的关键字
*/
int searchBin(int *p_start ,int length,int key){
int low=0;
int high=length-1;
int mid=-1;
while(low <=high){
mid=(low+high)/2;
if(p_start[mid]==key){
return mid;//查找成功
}else if(p_start[mid]>key){//待查记录在低半区间
high=mid-1;
}else{//p_start[mid]<key ,待查记录在高半区间
low=mid+1;
}
}
return -1;//查找不成功
}
int main(){
int list[ARRAY_SIZE]={5,13,19,21,37,56,64,75,80,88,92};
cout<<"待查找序列："<<endl;
myshow(list,ARRAY_SIZE);
int index=-1;
for(int i=0;i<ARRAY_SIZE;i++){
index =searchBin(list,ARRAY_SIZE,list[i]);
cout<<"查找"<<list[i]<<"返回下标为："<<index<<endl;
}
index =searchBin(list,ARRAY_SIZE,100);
cout<<"查找"<<100<<"返回下标为："<<index<<endl;
return 0;
}
运行结果：
4>时间及空间复杂度
