# 简要描述
**二分查找**又称折半查找，对排好序的数组，每次取这个数和数组中间的数进行比较，复杂度是O(logn)如:设数组为a[n],查找的数x,
如果x==a[n/2]，则返回n/2;
如果x < a[n/2]，则在a[0]到a[n/2-1]中进行查找；
如果x > a[n/2]，则在a[n/2+1]到a[n-1]中进行查找；
**优点**是比较次数少，查找速度快，平均性能好；其**缺点**是要求待查表为有序表，且插入删除困难。
条件：**查找的数组必须要为有序数组。**
# 二种实现方式
### 1.递归
~~~
/*
归的二分查找
arrat：数组 ， low:上界； high:下界; target:查找的数据； 返回target所在数组的下标
*/
int binarySearch(int array[], int low, int high, int target) {
int middle = (low + high)/2;
if(low > high) {
return -1;
}
if(target == array[middle]) {
return middle;
}
if(target < array[middle]) {
return binarySearch(array, low, middle-1, target);
}
if(target > array[middle]) {
return binarySearch(array, middle+1, high, target);
}
}
~~~
### 2.非递归（循环）
~~~
/*
非递归的二分查找
arrat：数组 ， n:数组的大小; target:查找的数据； 返回target所在数组的下标
*/
int binarySearch2(int array[], int n, int target) {
int low = 0, high = n, middle = 0;
while(low < high) {
middle = (low + high)/2;
if(target == array[middle]) {
return middle;
} else if(target < array[middle]) {
high = middle;
} else if(target > array[middle]) {
low = middle + 1;
}
}
return -1;
}
~~~
推荐使用非递归的方式，因为递归每次调用递归时有用堆栈保存函数数据和结果。**能用循环的尽量不用递归。**
# 二分查找的应用
还是对上一篇博文《[C++如何跳出多层循环](http://blog.csdn.net/luoweifu/article/details/16369007)》中提到的抽签问题进行分析。
上一篇博文中是进行了四重循环的嵌套，基时间复杂度是O(n4)，数据大时其计算量会大的惊人。为便于分析，将之前代码帖至如下：
<table style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'Times New Roman'"/><pre code_snippet_id="79771" snippet_file_name="blog_20131124_3_2823602" name="code" class="cpp">**
抽签问题
解决方案，复杂度n^4
*/
void drawLots() {
//从标准输入读入
int numOfCard, sum;
int k[MAX_N];
cout<<"输入numOfCard和sum"<<endl;
cin>>numOfCard>>sum;
cout<<"请输入这sum张卡片的数字"<<endl;
for(int i=0; i<numOfCard; i++) {
cin>>k[i];
}
bool result = false;
bool isBreakLoop = true;
int _sum = 0;
for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
for(int c = 0; c < numOfCard && isBreakLoop; c++) {
for(int d = 0; d < numOfCard && isBreakLoop; d ++) {
_sum = k[a] + k[b] + k[c] + k[d];
if(_sum == sum) {
result = true;
isBreakLoop = false;
}
}
}
}
}
cout << "_sum:" << _sum << " " << "sum:" << sum << endl;
if(result){
cout<<"Yes"<<endl;
} else
cout<<"No"<<endl;
}</pre><br/></td></tr></tbody></table>
最内层循环所做事如下：
Ka + kb + kc + kd = m
移项后如下:
Kd = m - (Ka + kb + kc)
到第四层循环时，其实Ka ，kb，kc已经知道，那问题也就变成了对kd的查找，我们可用上面讲的二分查找，复杂度就降为O(n3logn).实现如下：
### 降低复杂度的实现
<table style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'Times New Roman'"/><pre code_snippet_id="79771" snippet_file_name="blog_20131124_4_6902020" name="code" class="cpp">/**
抽签问题
解决方案，复杂度n^3 * log(n)
*/
void drawLots2() {
int numOfCard, sum;
int k[MAX_N];
cout<<"输入numOfCard和sum"<<endl;
cin>>numOfCard>>sum;
cout<<"请输入这sum张卡片的数字"<<endl;
for(int i=0; i<numOfCard; i++) {
cin>>k[i];
}
//对数组进行排序
sort(k, k + numOfCard);
int index = -1;
bool isBreakLoop = true;
for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
for(int c = 0; c < numOfCard && isBreakLoop; c++) {
index = binarySearch2(k, numOfCard, sum - (k[a] + k[b] + k[c]));
if(index >= 0) {
isBreakLoop = false;
}
}
}
}
if(index >= 0){
cout<<"Yes"<<endl;
} else
cout<<"No"<<endl;
}</pre><br/></td></tr></tbody></table>
### 进一步优化[O(n2logn)]
根据上一步的优化方式，我们可以进一步对内侧两层循环(也就是第三层和第四层)进行思考：
Kc+ kd = m - (Ka + kb )
我们不能直接对Kc+ kd进行查找，但是可以预先枚举出Ka + kb 的n2种数值并排序，再对Kc+ kd进行十分查找。列出枚举O(n2)，排序O(n2logn), 循环O(n2logn)，所以总的复杂度降为O(n2logn)，实现如下：
<table style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'Times New Roman'"/><pre code_snippet_id="79771" snippet_file_name="blog_20131124_5_6204692" name="code" class="cpp">/**
抽签问题
解决方案，复杂度n^2 * log(n)
*/
void drawLots3() {
int numOfCard, sum;
int k[MAX_N];
cout<<"输入numOfCard和sum"<<endl;
cin>>numOfCard>>sum;
cout<<"请输入这sum张卡片的数字"<<endl;
for(int i=0; i<numOfCard; i++) {
cin>>k[i];
}
int cdNum = numOfCard*(numOfCard+1)/2;
int cdSum[cdNum];
int i = 0;
for(int a=0; a<numOfCard; a++) {
for(int b=i; b<numOfCard; b++) {
cdSum[i ++] = k[a] + k[b];
}
}
//对数组进行排序
sort(cdSum, cdSum + cdNum);
int index = -1;
bool isBreakLoop = true;
for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
for(int c = 0; c < numOfCard && isBreakLoop; c++) {
index = binarySearch2(cdSum, cdNum, sum - (k[a] + k[b]));
if(index >= 0) {
isBreakLoop = false;
}
}
}
}
if(index >= 0){
cout<<"Yes"<<endl;
} else
cout<<"No"<<endl;
}</pre><br/></td></tr></tbody></table>
### 进一步思考
上面枚举Ka + kb 时其实是有重复的，因为k[i] + k[j] == k[j] + k[i]，去除重复值之后，Ka + kb 值的个数是n(n+1)/2。至于n(n+1)/2怎么来，可以简单推导如下：
N M
1 1
2 2+1
3 3+2+1
4 4+ 3+2+1
......
实现如下：
<table style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><p class="p0" style="margin:0pt; text-align:justify; font-size:10.5pt; font-family:'Times New Roman'"><span style="font-family:宋体; font-size:10.5pt"/></p><pre code_snippet_id="79771" snippet_file_name="blog_20131124_6_283111" name="code" class="cpp">/**
抽签问题
解决方案，复杂度n^2 * log(n)
*/
void drawLots3_1() {
int numOfCard, sum;
int k[MAX_N];
cout<<"输入numOfCard和sum"<<endl;
cin>>numOfCard>>sum;
cout<<"请输入这sum张卡片的数字"<<endl;
for(int i=0; i<numOfCard; i++) {
cin>>k[i];
}
int cdNum = numOfCard*numOfCard;
int cdSum[cdNum];
for(int a=0; a<numOfCard; a++) {
for(int b=0; b<numOfCard; b++) {
cdSum[a*numOfCard + b] = k[a] + k[b];
}
}
//对数组进行排序
sort(cdSum, cdSum + cdNum);
int index = -1;
bool isBreakLoop = true;
for(int a = 0; a < numOfCard && isBreakLoop; a ++) {
for(int b = 0; b < numOfCard && isBreakLoop; b ++) {
for(int c = 0; c < numOfCard && isBreakLoop; c++) {
index = binarySearch2(cdSum, cdNum, sum - (k[a] + k[b]));
if(index >= 0) {
isBreakLoop = false;
}
}
}
}
if(index >= 0){
cout<<"Yes"<<endl;
} else
cout<<"No"<<endl;
}</pre> </td></tr></tbody></table>
