任务 -- 此代码问题的目标是实现二分搜索算法。
输入格式 -- 输入的第一行包含一个整数n和一个序列a0< a1 < ... < an−1 of n pairwise distinct positive integers in increasing order. The next line contains an integer k and k positive integers b0,b1,...,bk−1.
约束 -- 1 ≤ n,k ≤ 10^4;对于所有 0 ≤ i ,1 ≤ a[i] ≤ 10^9 < n; 1 ≤ b[]j ≤ 10^9 for all 0 ≤ j < k;
输出格式 -- 对于从 0 到 k−1 的所有 i,输出索引 0 ≤ j ≤ n−1,使得 aj = bi 或 -1(如果没有这样的索引)。
我正在使用 c++11 编译器的代码块。 我已经尝试过压力测试并在我的系统中得到了正确的结果。 但 coursera 自动评分器给了我未知信号 11。 在某些问题中,它会给出未知信号 8。 谁能告诉我这背后可能的原因。
int binary_search(const vector<long long> &a, long long x) {
size_t left = 0, right = (size_t)a.size()-1;
size_t mid = 0;
while(left<=right){
mid = (left+right)/2;
if(x < a[mid]){
right = mid-1;
}
else if(x > a[mid]){
left = mid+1;
}
else return mid;
}
return -1;
}
int main() {
size_t n;
std::cin >> n;
vector<long long> a(n);
for (size_t i = 0; i < a.size(); i++) {
std::cin >> a[i];
}
size_t m;
std::cin >> m;
vector<long long> b(m);
for (size_t i = 0; i < m; ++i) {
std::cin >> b[i];
}
for (size_t i = 0; i < m; ++i) {
//replace with the call to binary_search when implemented
std::cout << binary_search(a, b[i]) << ' ';
}
}
我在自动评分器中得到的实际结果。
Failed case #4/36: unknown signal 11 (Time used: 0.00/1.00, memory used: 40071168/536870912.)
如果向量有例如大小 2,然后初始化
left = 0
、right = 1
和 mid = 0
。 left <= right
,因此您可以计算 mid = 0
并检查是否为 x < a[0]
。 如果发生这种情况,您现在设置right = -1
。在无符号算术中,这是一个非常大的数字。您的循环继续,因为 0 <= really large number
,您计算 mid = half of really large number
并访问那里的向量。那是 UB 并会让你的程序被杀死。
切换到有符号类型意味着
right = -1
确实小于left = 0
并终止循环。
不了解 Coursera 测试用例,但你的代码肯定会因两个边缘情况而失败:
1) 空输入向量
a
-> 你会在第 right = (size_t)a.size()-1;
行中得到下溢。换句话说,right
将成为一个大的正值,您将进入循环并尝试检索a[mid]
,其中mid
将是一些大的正索引。当然,尝试从空数组中获取它会导致错误。
2)
left+right
太大 -> 溢出 -> 在许多二分搜索实现中发现的错误,甚至在书中:) 请改用 mid = (right - left) / 2 + left
;
通过将所有
size_t
更改为 long
,它可以正常工作。
未知信号 11 表示分段错误,即内存访问出现问题。
因此,将所有 size_t
更改为 long
会增加 vector
的范围,从而允许容纳更多值,从而解决内存访问问题。
你的代码是否只需要改为
long
,其中有size_t
?因为我遇到了与您相同的问题 - unknown signal 11
(但在测试用例 12 中),并且在 Coursera 上与您的课程相同。我什至复制了您的代码并将所有 size_t
更改为 long
,将 int
更改为 long
作为 binary_search
变量类型,但仍然设置相同的结果。希望您尽快回复以帮助我克服这个问题!