二分查找的一个小问题

Question

首先给出可以运行代码：

#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...

Answer 1

已经找到问题所在了，确实是不应该将业务逻辑写在算法之中，主要还是因为没有判断其他的逻辑。
修正代码如下：

#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;
}