二分法+时间复杂度

二分法+时间复杂度

蒜头君手上有个长度为 n 的数组 A。由于数组实在太大了，所以蒜头君也不知道数组里面有什么数字，所以蒜头君会经常询问整数 x 是否在数组 A 中。

输入格式

第一行输入两个整数 n 和 m，分别表示数组的长度和查询的次数。

接下来一行有 n 个整数 ai​。

接下来 m 行，每行有 1 个整数 x，表示蒜头君询问的整数。

输出格式

对于每次查询，如果可以找到，输出"YES"，否则输出"NO"。

数据范围

1≤n,m≤105,0≤x≤106。

输入样例

10 5
1 1 1 2 3 5 5 7 8 9
0
1
4
9
10

输出样例

NO
YES
NO
YES
NO

解题思路：1.先输入两个整数 n 和 m，分别表示数组的长度和查询的次数。

2.接下来一行有 n 个整数 。

3.定义一个函数进行快速排序。

4.将排好序的数组利用二分法算法查找。

5.按照要求进行查找。

6.二分法查找完后按要求输出结果。

#include
#include
int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;

}
int main()
{
    int n,i, m,key, a[9999],low,hight,mid;//定义变量及数组
    scanf_s("%d%d", &n, &m);//输入数组的长度n及查询的次数m
    for (i = 0; i < n; i++) {
        scanf_s("%d", &a[i]);//输入数存入数组
    }
    qsort(a, n, sizeof(a[0]), cmp);
    for (i = 0; i < m; i++) {
        int d = 0, flag = 0;
        low = 0;
        hight = n - 1;
        scanf_s("%d", &key);//输入要找的数
        while (low <= hight) {
            mid = (low + hight) / 2;//找到最中间的数
            if (d == m) break;
            if (a[mid] < key)//如果最中间的数小于要找的数
            {
                d++;
                low = mid+1;//则在数列的后半段中查找
            }
            else if (a[mid] > key) {//如果最中间的数大于要查找的数
                d++;
                hight = mid-1 ;//则在数列的前半段中查找
            }
            else {
                flag = 1;
                break;
            }
        }
        if (flag == 1) printf("YESn");//若找到输出yes
        else printf("NOn");//没找到输出no
    }
    return 0;
}