二分练习

本文主要是介绍二分练习，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

二分练习

Description
给你一个序列，然后给你m个元素，让你从序列中找出与每个元素最接近的数字输出来，如果有两个就输出两个。

Input
多组输入，第一行给你两个数n（0 < n < 10000000）,m(0 < m < n),接下来是数列的n个数，然后再输入m个元素，让你找出最接近每个元素的值。如果有两个，按从小到大输出。

Output
这m个数分别输出最接近每个元素的值，组与组之间输出一个空行。
Sample
Input
8 4
1 2 3 4 5 6 8 11
4
9
2
7
Output
4
8
2
6 8
Hint

思路： 比起一般的二分，更难一些。如果没找到要找的数，就要输出距离最近的数。所以需要处理左右两边的数，还要处理边界的问题。用二分找出来的数，要与你要找的数，进行对比，一样就输出这个数。
不一样，就看你二分出来的数（这里如果我没找到的话，我选择的是比要找的数小的最大的数，那它右边就是比要找的数大的数，记作left，right）left和right和目标数看谁更接近，就输出谁，一样的话，就都输出。
代码放在下面。思路已写，注释略写。（主要还是我要记笔记，和练习自己的二分能力）

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10000010;
int a[N];
int ex_find(int l,int r,int k) { //二分
    int mid;
    while(l<=r) {
        mid=(l+r)/2;
        if(a[mid]==k) return mid;
        else if(a[mid]>k) r=mid-1;
        else if(a[mid]<k) l=mid+1;
    }
    if(a[mid]<=k) return mid;
    else return mid-1;
}

int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)) {
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        sort(a,a+n);
        while(m--) {
            int k;
            scanf("%d",&k);
            if(k>=a[n-1]) {  //处理边界，找的数比最大的数还大就直接输出最大的数
                printf("%d\n",a[n-1]);
                continue;
            }
            else if(k<=a[0]) { //同上
                printf("%d\n",a[0]);
                continue;
            }
            int now=ex_find(0,n-1,k);  //下面写的就与思路一样了
            if(a[now]==k) {
                printf("%d\n",a[now]);
            }
            else {
                if(k-a[now]==a[now+1]-k) {
                    printf("%d %d\n",a[now],a[now+1]);
                }
                else if(k-a[now]<a[now+1]-k) {
                    printf("%d\n",a[now]);
                }
                else if(k-a[now]>a[now+1]-k) {
                    printf("%d\n",a[now+1]);
                }
            }
        }
    }
    return 0;
}

To be continued
如果你有任何建议或者批评和补充，请留言指出，不胜感激

这篇关于二分练习的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！