二分练习

刺骨的言语ヽ痛彻心扉 2022-07-12 11:45 117阅读 0赞

think:  
1感觉自己的二分查找时候有点繁琐了，判断条件用的有点多，一开始没有发现如果查找的最后一组数据即a\[i\] = a\[j\] = a\[mid\] = x的时候机会无输出，  
尝试测试有幸发现了自己的错误  
2自己先用快排函数对输入数据进行排序，然后用二分查找的思想进行查找，找到之后还要判断那个点与x之间的关系，还要判断临界条件，显得比较繁琐，但对思维的压力练习还是很有益的，作为理工科的学生，逻辑严密，思维严谨，如果具备这样优秀的习惯基本做什么事情都会游刃有余

[sdut原题链接][sdut]

二分练习  
Time Limit: 1000MS Memory Limit: 65536KB

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

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

Output  
这m个数分别输出最接近每个元素的值，组与组之间输出一个空行。

Example Input  
8 4  
1 2 3 4 5 6 8 11  
4  
9  
2  
7

Example Output  
4  
8  
2  
6 8

Hint

Author  
lwn

以下为accepted代码

#include <stdio.h>
    #include <stdlib.h>
    int book[10000004];
    int cmp(const void *a, const void *b)
    {
        return ((*(int *)a) - (*(int *)b));
    }
    void Second_Search(int x, int left, int right)
    {
        int i = left, j = right;
        int mid = (i + j)/2;
        while(i < j)
        {
            if(book[mid] == x)
            {
                printf("%d\n", x);
                return;
            }
            else if(book[mid] < x)
            {
                i = mid + 1;
                mid = (i + j)/2;
            }
            else if(book[mid] > x)
            {
                j = mid - 1;
                mid = (i + j)/2;
            }
        }
        if(book[i] == x)
            printf("%d\n", x);
        if(book[i] > x)
        {
            if(i == left)
                printf("%d\n", book[i]);
            else
            {
                if(book[i] - x < x - book[i-1])
                {
                    printf("%d\n", book[i]);
                }
                else if(book[i] - x > x - book[i-1])
                {
                    printf("%d\n", book[i-1]);
                }
                else
                {
                    printf("%d %d\n", book[i-1], book[i]);
                }
            }
        }
        else if(book[i] < x)
        {
            if(i == right)
                printf("%d\n", book[right]);
            else
            {
                if(x - book[i] < book[i+1] - x)
                {
                    printf("%d\n", book[i]);
                }
                else if(x - book[i] > book[i+1] - x)
                {
                    printf("%d\n", book[i+1]);
                }
                else
                    printf("%d %d\n", book[i], book[i+1]);
            }
        }
    }
    int main()
    {
        int n, m, i, x;
        while(scanf("%d %d", &n, &m) != EOF)
        {
            for(i = 0; i < n; i++)
                scanf("%d", &book[i]);
            qsort(&book[0], n, sizeof(book[0]), cmp);
            for(i = 0; i < m; i++)
            {
                scanf("%d", &x);
                Second_Search(x, 0, n-1);
            }
            printf("\n");
        }
        return 0;
    }
    
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 728ms
    Take Memory: 364KB
    Submit time: 2017-02-22 20:47:00
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2018/pid/2781