二分查找算法
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
算法要求:
1.必须采用顺序存储结构
.2.必须按关键字大小有序排列。
下面是c++与java的不同实现:
已经假设所查询数组均为升序排列好了:
C++版:
#include <iostream>
#include <stdlib.h>
#define ERROR -1
#define LEN 10
using namespace std;
/************************************************************************/
/* T 自定义数据类型
value 查找的值
low 左侧边界 (一般为0)
high 右侧边界(一般为数组长度-1)
/************************************************************************/
template <class T>
int binarySearch(T table[],T value,int low,int hign){
if(low<=hign){//边界有效
int mid = (low+hign)/2; //找到中间点
if(table[mid]==value){//如果中间点的值就是我们查找的值,则返回该点
return mid;
}else if(table[mid]>value){//如果中间值比查找值大,则证明查找的值在中间点的左侧
return binarySearch(table,value,low,mid-1);//继续将范围缩小到原来一半(靠左缩小)
}else{
return binarySearch(table,value,mid+1,hign);//继续将范围缩小到原来一半(靠右缩小)
}
}
return ERROR;
}
/************************************************************************/
/* 由上述代码可以知道,上边界和和下边界其实就是数组的开始和结束位置,因此上述函数可以泛化为下列函数 */
/************************************************************************/
template <class T>
int binarySearch(T table[],int n,T value){
return binarySearch(table,value,0,n-1);
}
template <class T>
void print(T table[],int n){
for (int i=0;i<n;i++)
{
cout<<table[i]<<" ";
}
cout<<"\n";
}
int main(void){
//给出一个已经排序好的数组
int array[LEN] = {0};
for (int i=0;i<LEN;i++)
{
array[i] = i+10;
}
cout<<"您要查找的序列为:";
print(array,LEN);
cout<<"请输入你要查找的内容:";
int search;
cin>>search;
//调用函数
int searchResult = binarySearch(array,LEN,search);
cout<<"查找内容为"<<search<<"在指定数组的第"<<(searchResult+1)<<"处"<<endl;
system("pause");
return 1;
}