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

标签 c++ binary-search

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;
}

最佳答案

您无需重新发明轮子。可以使用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 并节省一些内存。

如果您仍然遇到超时问题,则可能是输入/输出速度较慢。尝试在 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

关于c++ - 修改后的二进制搜索算法超过时间限制,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53138462/

相关文章:

c++ - struct 中的 std::string - 复制/分配问题?

c++ - 如何获得成功的 binary_search 的迭代器?

java - 什么算作二分搜索比较?

java - 使用二进制搜索在正确的索引处打开数组中的空间

algorithm - 快速插入有序数组

c++ - 简单的设计选择?

c++ - 无法访问的继承公共(public)属性(property)

c++ - 如何通过 C++ 库读取多帧 DICOM 文件?

c++ - 如何在 C++/Linux 中创建目录树?

algorithm - 为了更快速地搜索,难道不应该在进行二分搜索之前对数据应用合并排序,还是直接跳到线性搜索?