修改后的二进制搜索算法超过时间限制

Question

You are given a sorted array of numbers, and followed by number of queries, for each query if the queried number is present in the array print its position, else print -1.

Input

First line contains N Q, number of elements in the array and number of queries to follow,

Second line contains N numbers, elements of the array, each number will be -10^9<= ai <= 10^9, 0 < N <= 10^5, 0 < Q <= 5*10^5

参考：https://www.spoj.com/problems/BSEARCH1/

我的代码在终端上运行正常，但它超过了在线判断的时间限制，即使它需要 O(NQ) 时间。

这是我的代码：

#include <iostream>

long long binarySearch(long long arr[], long long l , long long r , long long x) {
    long long mid;
    if (r >= l){ 
        mid = (l+r)/2;
        if (arr[mid] == x) {
            if (arr[mid] == arr[mid-1]) {
                while (arr[mid] == arr[mid-1]) {
                    --mid;
                }
                return mid;
            }
            else{
                return mid;
            }
        } 
        if (arr[mid] > x) {
            return  binarySearch(arr,l,mid-1,x);
        } 
        if (arr[mid] < x) {
            return binarySearch(arr,mid+1,r,x);
        }
    }
    return -1;
}

int main() {
    long long n ,q;
    std::cin >> n >> q;
    long long array[n];
    for (long long i = 0; i < n; ++i) {
        std::cin >> array[i];
    }
    long long x;
    long long arr2[q];
    for (long long i = 0 ; i < q ; ++i) {
        std::cin >> x;
        std::cout << binarySearch(array,0,n-1,x) << "\n";

    }
    return 0;
}

Answer 1

我想你要做的是打印找到的元素的第一个位置。但是，如果您有一个所有元素都相同的数组 1,1,1,1,1,1,1，那么您基本上是对一个查询执行 O(n)，这会导致 O(nq)，其中 n 是数组的长度，q 是最坏情况下的查询次数。

建议：我认为你需要做的是去掉重复项。

对数组进行排序。
创建另一个对数组（如 std::vector<std::pair<int,int>。以 (element, first-pos) 作为对。
然后对其进行二分查找

Answer 2

我认为主要问题是您的二分查找实现是递归。

我不知道本地输入数据是否非常大以测试您的实施是否合适。但是如果像this example那样把实现递归改成迭代，代码的性能会得到提升

迭代实现优于递归的原因，查看this。

请注意，编译器具有 尾调用优化 功能，可以消除递归实现速度的降低。

Answer 3

您不需要重新发明轮子。可以使用C++标准库算法std::lower_bound。它对值可能存在的第一个位置进行二进制搜索。

您可以按如下方式重写您的函数：

#include <algorithm>

long long binarySearch(long long arr[], long long n, long long x)
{
    // O(log n) binary search for first element not less that x
    long long *itr = std::lower_bound(arr, arr + n, x);

    // If itr is array end or location doesn't contain x
    if (itr == arr + n || *itr != x) {
        return -1;
    }

    // Compute index by address arithmetic
    return itr - arr;
}

我删除了一个不必要的函数参数，只传递数组大小。顺便说一下，这个问题不需要 long long。不妨使用 int 并节省一些内存。

如果您仍然遇到超时问题，它可能会变慢 input/output。尝试在 main().

的开头添加接下来的两行

std::ios_base::sync_with_stdio(false); // possibly faster I/O buffering
std::cin.tie(NULL); // don't flush output stream before doing input

修改后的二进制搜索算法超过时间限制

Modified Binary Search algorithm exceeding time limit

c++

binary-search