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

Question

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

输入格式 -- 输入的第一行包含一个整数 n 和一个序列 a0 < a1 < ... < an−1，其中 n 个成对不同的正整数按升序排列。下一行包含一个整数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

如果 vector 具有例如大小 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并在那里访问 vector 。那是 UB 并且会杀死您的程序。

切换到签名类型意味着 right = -1确实小于left = 0并终止循环。