如何降低多查询二分查找的时间复杂度？超时问题求助

问题根源 #

你当前使用的插入排序时间复杂度为O(n²)，当n达到1e5时，总操作次数会突破1e10级别，远远超过1秒内CPU可处理的运算量（通常约1e8次），这是导致超时的核心原因。

另外，代码还存在两处细节问题：

• 二分查找找到目标值后未立即终止循环，会执行多余的迭代逻辑；
• 交换元素时使用int temp，但数组元素是long long类型，会导致数据截断引发错误。

优化方案 #

1. 替换为高效排序算法 #

使用C标准库的qsort函数，它实现了平均时间复杂度O(n log n)的快速排序，完全能处理1e5规模的数据。

2. 优化二分查找逻辑 #

找到目标值后立即设置标记并退出循环，避免无意义的迭代。

3. 修正变量类型错误 #

将交换用的temp改为long long类型，匹配数组元素的类型。

修改后的代码 #

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

// qsort的比较函数，用于long long类型的升序排序
int compare(const void *a, const void *b) {
    long long num1 = *(const long long *)a;
    long long num2 = *(const long long *)b;
    if (num1 < num2) return -1;
    if (num1 > num2) return 1;
    return 0;
}

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    // 动态分配数组，避免n=1e5时栈溢出
    long long int *a = malloc(n * sizeof(long long));
    if (!a) {
        perror("malloc failed");
        return 1;
    }

    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }

    // 用qsort替代插入排序
    qsort(a, n, sizeof(long long), compare);

    // 优化后的二分查找
    long long int x;
    for (int i = 0; i < q; i++) {
        scanf("%lld", &x);
        int l = 0, r = n - 1;
        int found = 0;
        while (l <= r) {
            // 避免l+r溢出的mid计算方式
            int mid = l + (r - l)/2;
            if (a[mid] == x) {
                found = 1;
                break; // 找到后立即退出循环
            } else if (a[mid] < x) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        printf(found ? "found\n" : "not found\n");
    }

    free(a);
    return 0;
}

额外优化说明 #

• 改用malloc动态分配数组：当n=1e5时，栈上的静态数组可能超出系统默认栈大小（通常为几MB），引发栈溢出错误，动态分配更安全；
• 二分查找中mid = l + (r-l)/2的写法：避免l + r超出int范围导致的溢出问题。

内容的提问来源于stack exchange，提问作者Didar004