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/