# 二分查找的一个小问题

136 views

### 二分查找的一个小问题

#### 首先给出可以运行代码：

``````#include <cstdio>
#include <algorithm>

using namespace std;

int binarySearch(int left,int right,int num,int coins[]){
int mid;
while (left<=right){
mid = left + (right-left)/2;
if(coins[mid]==num){
return mid;
} else if (coins[mid]<num){
left = mid+1;
} else {
right = mid-1;
}
}
return -1;
}

int main(){
int N,M;
scanf("%d %d",&N,&M);
int coins[N];
for(int i=0;i<N;++i){
scanf("%d",&coins[i]);
}
sort(coins,coins+N);
for (int j = 0; j < N; ++j) {
int mid;
int pos = binarySearch(0,N-1,M-coins[j],coins);
if(pos!=-1&&pos!=j){
printf("%d %d",coins[j],coins[pos]);
return 0;
}
}
printf("No Solution");
return 0;
}``````

#### 测试用例：

``````7 14
1 8 7 2 4 11 15``````

#### 输出结果：

``No Solution``

#### 问题代码如下：

``````#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
int N,M;
scanf("%d %d",&N,&M);
int coins[N];
for(int i=0;i<N;++i){
scanf("%d",&coins[i]);
}
sort(coins,coins+N);
for (int j = 0; j < N; ++j) {
//对于coins[j],查找M-coins[j]==coins[k]的k并且k!=j
int left=0,right=N-1;
int mid;
int num = M-coins[j];
while (left<=right){
mid = left + (right-left)/2;
if(coins[mid]==num){
if(mid!=j){
printf("%d %d",coins[j],coins[mid]);
return 0;
}
} else if (coins[mid]<num){
left = mid+1;
} else {
right = mid-1;
}
}
}
printf("No Solution");
return 0;
}``````

#### 题目来源：

https://pintia.cn/problem-set...

by (71.8m points)

``````#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
int N,M;
scanf("%d %d",&N,&M);
int coins[N];
for(int i=0;i<N;++i){
scanf("%d",&coins[i]);
}
sort(coins,coins+N);
for (int j = 0; j < N; ++j) {
//对于coins[j],查找M-coins[j]==coins[k]的k并且k!=j
int left=0,right=N-1;
int mid;
int num = M-coins[j];
int k = -1;
while (left<=right){
mid = left + (right-left)/2;
if(coins[mid]==num){
k = mid;
break;
} else if (coins[mid]<num){
left = mid+1;
} else {
right = mid-1;
}
}
if(k!=j&&k!=-1){
printf("%d %d",coins[j],coins[k]);
return 0;
}
}
printf("No Solution");
return 0;
}``````