Код работает нормально в моей системе, но Coursera Autograder дает мне неизвестный сигнал

Question

Задача - Целью этой проблемы кода является реализация алгоритма двоичного поиска.

Формат ввода - Первая строка ввода содержит целое число n и последовательность a0

Ограничения - 1 ≤ n, k ≤ 10 ^ 4; 1 ≤ a [i] ≤ 10 ^ 9 для всех 0 ≤ i

Формат вывода - Для всех i от 0 до k − 1 выведите индекс 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]) << ' ';
  }
}

Фактический результат, который я получил в автогрейдере.

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

Answer 1

Если вектор имеет, например, размер 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 и завершает цикл.

Answer 2

Не знаю о тестовых случаях Coursera, но ваш код определенно потерпит неудачу с двумя крайними случаями:

1) пустой входной вектор a -> вы получите недопустимое значение в строке right = (size_t)a.size()-1;.Другими словами, right станет большим положительным значением, вы войдете в цикл и попытаетесь получить a[mid], где mid будет большим положительным индексом.Конечно, попытка получить это из пустого массива приведет к ошибке.

2) left+right слишком большой -> переполнение -> ошибка, найденная во многих реализациях двоичного поиска, даже в книгах :) Используйте вместо этогоmid = (right - left) / 2 + left;

Answer 3

Изменяя все size_t на long, он работает правильно. неизвестный сигнал 11 означает ошибка сегментации , то есть что-то не так с доступом к памяти. Таким образом, изменяя все size_t на long, вы увеличиваете диапазон vector и, следовательно, добавляете больше значений, что решает проблему доступа к памяти.