时间戳

首页 > 解决方案 > 修改后的二分搜索算法超过时间限制

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

问题描述

您将获得一个排序的数字数组，然后是查询数，对于每个查询，如果查询的数字存在于数组中，则打印其位置，否则打印 -1。

输入

第一行包含 NQ、数组中的元素数和要遵循的查询数，

第二行包含 N 个数字，数组元素，每个数字将是 -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++binary-search

解决方案

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

意见建议：我认为你需要做的是摆脱重复。

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

推荐阅读