# 簡要描述
**二分查找**又稱折半查找,對排好序的數組,每次取這個數和數組中間的數進行比較,復雜度是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>