数据结构上机实验之二分查找

男娘i 2022-05-15 04:06 128阅读 0赞

### 数据结构上机实验之二分查找 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][] [Discuss][]

Problem Description

在一个递增的序列里，查找元素是否存在，若存在输出YES,不存在输出NO.

Input

本题多组数据，首先输入一个数字n(n>=100000)，然后输入n个数，数据保证数列递增，然后再输入一个查找数字。

Output

若存在输出YES,不存在输出NO.

Sample Input

4
    1 3 5 8
    3

Sample Output

YES

Hint

Source

#include <stdio.h>
    #include <stdlib.h>
    int a[100101];
    int find(int a[], int l, int r, int key)
    {
        int mid;
        int i, j;
        i = l, j = r, mid = (i+j) / 2;
        while(i <= j)
        {
            if(a[mid] == key)
            {
                return mid;
            }
            else if(a[mid] < key)
            {
                return find(a,mid+1,j,key);
            }
            else
            {
                return find(a,i,mid-1,key);
            }
        }
        return -1;
    }
    int main()
    {
        int n, m, i, num, key;
        while(scanf("%d", &n) != EOF)
        {
            for(i = 0; i< n; i++)
            {
                scanf("%d", &a[i]);
            }
            scanf("%d", &key);
            num = find(a,0,n-1,key);
            if(num == -1)
            {
                printf("NO\n");
            }
            else
            {
                printf("YES\n");
            }
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/submitsolution/pid/2039.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/status/pid/2039.html
[Discuss]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Discuss/discusslist/pid/2039.html