顺序表应用6：有序顺序表查询

我不是女神ヾ 2022-05-11 02:46 158阅读 0赞

### 顺序表应用6：有序顺序表查询 ###

Time Limit: 1000 ms Memory Limit: 4096 KiB

[Submit][] [Statistic][]

Problem Description

顺序表内按照由小到大的次序存放着n个互不相同的整数，任意输入一个整数，判断该整数在顺序表中是否存在。如果在顺序表中存在该整数，输出其在表中的序号；否则输出“No Found!"。

Input

第一行输入整数n (1 <= n <= 100000)，表示顺序表的元素个数；  
第二行依次输入n个各不相同的有序非负整数，代表表里的元素；  
第三行输入整数t (1 <= t <= 100000)，代表要查询的次数；  
第四行依次输入t个非负整数，代表每次要查询的数值。

保证所有输入的数都在 int 范围内。

Output

输出t行，代表t次查询的结果，如果找到在本行输出该元素在表中的位置，否则本行输出No Found!

Sample Input

10
    1 22 33 55 63 70 74 79 80 87
    4
    55 10 2 87

Sample Output

4
    No Found!
    No Found!
    10

Hint

Source

#include <stdio.h>
    #include <stdlib.h>
    typedef struct node
    {
        int data[100010];
        int last;
    } st;
    int erfeng(st *head, int l, int r, int key)
    {
        int i, j, mid;
        i = l;
        j = r;
        if(i <= j)
        {
            mid = (i + j) / 2;
            if(head->data[mid] == key)
            {
                return mid;
            }
            else if(head->data[mid] > key)
            {
                return erfeng(head,l,mid-1,key);
            }
            else
            {
                return erfeng(head,mid+1,r,key);
            }
        }
        return -1;
    }
    int main()
    {
        st *head;
        int n, i;
        scanf("%d", &n);
        head = (st *)malloc(sizeof(st));
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &head->data[i]);
        }
        int t;
        scanf("%d", &t);
        while(t--)
        {
            int num, x;
            scanf("%d", &x);
            num = erfeng(head,1,n,x);
            if(num == -1)
            {
                printf("No Found!\n");
            }
            else
            {
                printf("%d\n", num);
            }
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2579/pid/3330.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2579/pid/3330.html