小金的询问——二分查找

朴灿烈づ我的快乐病毒、 2022-06-16 02:42 147阅读 0赞

Think:  
1有序数组+查询，思考可否用二分查找（二分法思想）

[sdut题目链接][sdut]

小金的询问  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
给定一个有序（升序）数字数组A，查找数字target，若target在数组中出现，返回位置，若不存在，返回它应该插入的位置

Input  
多组输入。  
每组输入第一行输入两个整数n，m，分别代表数组长度和询问次数；  
第二行输入n个整数，为数字A的所以元素，数据保证没有重复元素；  
接下来的m行，每行一个正整数表示询问的target。

Output  
若target在数组中出现，输出taeget的位置，若不存在，输出它应该插入的位置。

Example Input  
4 2  
1 2 3 4  
2  
0

Example Output  
2  
1

Hint

Author  
2015级《程序设计基础II》计科软件通信期末上机考试2

以下为Wrong Answer代码  
错误原因：相对较大值返回错误，题意理解不完全

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    int b[19980414];
    
    void Search(int a[], int left, int right, int x);
    
    int main()
    {
        int n, m, i, x;
        while(scanf("%d %d", &n, &m) != EOF){
            for(i = 1; i <= n; i++)
                scanf("%d", &b[i]);
            while(m--){
                scanf("%d", &x);
                Search(b, 1, n, x);
            }
        }
        return 0;
    }
    void Search(int a[], int left, int right, int x)
    {
        int k, i = left, j = right;
        if(i > j)
            return;
    
        if(a[i] > x){
            printf("%d\n", i);
            return;
        }
        else if(a[j] < x){
            printf("%d\n", j);
            return;
        }
    
        k = (i+j)/2;
        if(a[k] < x)
            Search(a, k+1, right, x);
        if(a[k] > x)
            Search(a, left, k-1, x);
        if(a[k] == x)
            printf("%d\n", k);
    }
    
    
    /***************************************************
    User name: 
    Result: Wrong Answer
    Take time: 56ms
    Take Memory: 464KB
    Submit time: 2017-05-03 15:22:29
    ****************************************************/

以下为Accepted代码

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    int b[19980414];
    
    void Search(int a[], int left, int right, int x);
    
    int main()
    {
        int n, m, i, x;
        while(scanf("%d %d", &n, &m) != EOF){
            for(i = 1; i <= n; i++)
                scanf("%d", &b[i]);
            while(m--){
                scanf("%d", &x);
                Search(b, 1, n, x);
            }
        }
        return 0;
    }
    void Search(int a[], int left, int right, int x)
    {
        int k, i = left, j = right;
        if(i > j)
            return;
    
        if(a[i] > x){
            printf("%d\n", i);
            return;
        }
        else if(a[j] < x){
            printf("%d\n", j+1);
            return;
        }
    
        k = (i+j)/2;
        if(a[k] < x)
            Search(a, k+1, right, x);
        if(a[k] > x)
            Search(a, left, k-1, x);
        if(a[k] == x)
            printf("%d\n", k);
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 52ms
    Take Memory: 508KB
    Submit time: 2017-05-03 15:33:12
    ****************************************************/

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