代码在我的系统中运行良好，但 coursera autograder 给我未知信号

Question

任务 -- 这道代码题的目标是实现二分查找算法。

输入格式 -- 输入的第一行包含一个整数 n 和一个序列 a0 < a1 < ... < an−1 of n pairwise distinct positive integers in增加订单。下一行包含一个整数k和k个正整数b0,b1,...,bk−1.

约束条件 -- 1 ≤ n,k ≤ 10^4; 1 ≤ a[i] ≤ 10^9 对于所有 0 ≤ i < n； 1 ≤ b[]j ≤ 10^9 对于所有 0 ≤ j < k;

输出格式 -- 对于从0到k−1的所有i，输出一个索引0≤j≤n−1使得aj=bi或者-1如果有没有这样的索引。

我正在使用带有 c++11 编译器的代码块。我已经尝试过压力测试并在我的系统中得到了正确的结果。但是 coursera autograder 给了我未知信号 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]) << ' ';
  }
}

我在 autograder 中得到的实际结果。

Failed case #4/36: unknown signal 11 (Time used: 0.00/1.00, memory used: 40071168/536870912.)

Answer 1

不了解 Coursera 测试用例，但您的代码肯定会因两种极端情况而失败：

1) 空输入向量 a -> 你会在行 right = (size_t)a.size()-1; 中遇到下溢。换句话说，right 将成为一个大的正值，您将进入循环并尝试检索 a[mid]，其中 mid 将是一些大的正索引。当然，尝试从空数组中获取它会导致错误。

2) left+right 太大 -> 溢出 -> 在许多二进制搜索实现中发现的错误，甚至在书中 :) 改用 mid = (right - left) / 2 + left;

Answer 2

通过将所有 size_t 更改为 long，它可以正常工作。 unknown signal 11 表示 segmentation fault，即内存访问有问题。因此，将所有 size_t 更改为 long 会增加 vector 的范围，从而让更多的值能够解决内存访问问题。

Answer 3

如果载体有例如大小 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 autograder 给我未知信号

Code is working fine in my system but coursera autograder is giving me unknown signal

c++

algorithm

binary-search

c++11

coursera-api