如何编码以在二分搜索中减少多个查询的时间复杂度？

Question

问题：

每次测试时间限制：1秒
每个测试的内存限制：256 MB
输入：标准输入
输出：标准输出

给定 2 个数字 N 和 Q，由 N 数字组成的数组 A 和 Q 查询，每个数字都包含一个数字 X。
对于每个查询，如果数组 A 中存在数字 X，则打印包含“找到”的单行，否则，打印“未找到”。

输入：

第一行包含两个数字 N, Q (1 ≤ N, Q ≤ 10⁵)。

第二行包含 N 个数字 (1 ≤ A_i ≤ 10⁹)。

接下来的 Q 行包含 X (1 ≤ X ≤ 10⁹)。

输出：

在一行中打印每个查询的答案。

示例： 输入

5 3
1 5 4 3 2
5
3
6

输出

found
found
not found

我的代码：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    long long int a[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
        //insertion sort, Ascending order
        int temp;
        for (int j = i; j > 0 && a[j] < a[j - 1]; j--)
        {
            temp = a[j];
            a[j] = a[j - 1];
            a[j - 1] = temp;
        }
    }

    //Binary Search
    long long int x, found = 0;
    for (int i = 0; i < q; i++)
    {
        scanf("%lld", &x);
        int l = 0, r = n - 1, mid;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if (a[mid] == x)
            {
                found=1;
            }
            if (a[mid] < x)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        if (found == 1)
        {
            printf("found\n");
        }
        else
        {
            printf("not found\n");
        }
        found = 0;
    }

    return 0;
}

我尝试在获取输入时对数组进行排序，并使用循环进行查询和二分搜索。提交后，此代码显示

Time limit exceeded on test 2

。我不知道如何降低这段代码的时间复杂度。请帮助我！

Answer 1

问题不在于每个查询的二分搜索的复杂性，而是插入排序阶段的复杂性，它是二次的。

您可以通过使用

qsort

对数组进行排序来降低复杂度（复杂度 N.log(N)），

您甚至可以将其减少为线性，因为您会得到一个重要提示：每个测试的内存限制：256 兆字节。因此，您可以使用长度为 10⁹ 的位数组（占用 128MB），并为每个数字设置相应的位 A_i 读入并测试每个查询的位。尽管因子很高，但它具有线性复杂度。

这是使用

qsort

的修改版本：

#include <stdio.h>
#include <stdlib.h>

int compare_long(const void *aa, const void *bb) {
    const long *a = aa;
    const long *b = bb;
    return (*a > *b) - (*a < *b);
}

int main(void)
{
    int n, q;
    if (scanf("%d %d", &n, &q) != 2)
        return 1;

    // long is enough for |Ai| <= 10**9
    long int *a = calloc(sizeof *a, n);
    if (a == NULL)
        return 1;

    for (int i = 0; i < n; i++) {
        if (scanf("%ld", &a[i]) != 1)
            return 1;
    }
    qsort(a, n, sizeof(*a), compare_long);

    for (int i = 0; i < q; i++) {
        long int x;
        if (scanf("%ld", &x) != 1)
            return 1;
        // Binary Search
        int l = 0, r = n;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (a[mid] <= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l < n && a[l] == x) {
            printf("found\n");
        } else {
            printf("not found\n");
        }
    }
    free(a);
    return 0;
}

如果仍然超出时间限制，您可以尝试使用基数排序来对数组进行排序，而不是

qsort

或使用位数组，如上所述。