re:re:actable
Урок 064 минуты чтения

Как избегать off-by-one и ошибок с границами?

На этой странице
Кратко

Off-by-one - ошибка на один индекс: взяли лишний элемент, пропустили последний или получили бесконечный цикл. Новичкам проще избегать таких ошибок через явный выбор интервала и dry run.

Вопрос

Как избегать off-by-one ошибок и ошибок с границами?

Что такое off-by-one

Пример ошибки:

for (let i = 0; i <= nums.length; i++) {
  console.log(nums[i])
}

Последний индекс массива:

nums.length - 1

Значит условие должно быть:

for (let i = 0; i < nums.length; i++) {
  console.log(nums[i])
}

Правило полуоткрытого интервала

В JS удобно думать в формате:

[start, end)

То есть:

  • start включен;
  • end не включен;
  • длина = end - start.

Пример:

for (let i = start; i < end; i++) {
  // i принадлежит [start, end)
}

Это совпадает с slice(start, end).

Индексы массива

Для массива длины n:

первый индекс = 0
последний индекс = n - 1
количество элементов = n

Если идем вперед:

for (let i = 0; i < nums.length; i++) {}

Если идем назад:

for (let i = nums.length - 1; i >= 0; i--) {}

Есть два популярных стиля.

Закрытый интервал [left, right]

let left = 0
let right = nums.length - 1
 
while (left <= right) {
  const mid = Math.floor((left + right) / 2)
 
  if (nums[mid] === target) return mid
  if (nums[mid] < target) left = mid + 1
  else right = mid - 1
}

Здесь right включен, поэтому:

  • старт right = nums.length - 1;
  • условие left <= right;
  • сдвиги mid + 1 и mid - 1.

Полуоткрытый интервал [left, right)

let left = 0
let right = nums.length
 
while (left < right) {
  const mid = Math.floor((left + right) / 2)
 
  if (nums[mid] < target) left = mid + 1
  else right = mid
}

Здесь right не включен, поэтому:

  • старт right = nums.length;
  • условие left < right;
  • правая граница становится mid, не mid - 1.

Главное - не смешивать стили.

Sliding window

Длина окна:

right - left + 1

если left и right включены.

best = Math.max(best, right - left + 1)

Для полуоткрытого окна [left, right) длина:

right - left

Выбери один стиль и держись его.

Prefix sums

Удобный prefix:

const prefix = new Array(nums.length + 1).fill(0)
 
for (let i = 0; i < nums.length; i++) {
  prefix[i + 1] = prefix[i] + nums[i]
}

Сумма диапазона [left, right]:

prefix[right + 1] - prefix[left]

Почему right + 1? Потому что prefix[i] хранит сумму первых i элементов, не включая индекс i.

Grid boundaries

function inBounds(row: number, col: number, rows: number, cols: number): boolean {
  return row >= 0 && row < rows && col >= 0 && col < cols
}

Всегда проверяй:

  • row >= 0;
  • row < rows;
  • col >= 0;
  • col < cols.

Мини-техника проверки

Проверь 3 размера:

n = 0
n = 1
n = 2

И 3 позиции:

первый элемент
последний элемент
элемент отсутствует

Если алгоритм работает на этих случаях, шанс off-by-one сильно ниже.

Что важно помнить: частые ошибки

  • Писать i <= nums.length.
  • Смешивать [left, right] и [left, right).
  • В binary search делать right = mid - 1 в полуоткрытом стиле.
  • Забывать right - left + 1.
  • В prefix sums забывать right + 1.
  • В grid проверять только верхнюю границу, забыв нижнюю.
  • Использовать while (left < right) там, где нужен поиск точного значения с закрытым интервалом.

Что отвечать на собеседовании?

Чтобы избежать off-by-one, я сначала выбираю модель интервала: закрытый [left, right] или полуоткрытый [left, right). Затем проверяю алгоритм на маленьких случаях: пустой input, один элемент, два элемента, первый/последний элемент. В binary search особенно важно не смешивать условие цикла и обновление границ.

Мини-шпаргалка

  • Последний индекс = length - 1.
  • В обычном цикле чаще i < length.
  • [start, end) проще для JS.
  • Binary search: выбери один стиль.
  • Window length: right - left + 1.
  • Prefix range: prefix[right + 1] - prefix[left].
  • Grid: 0 <= row < rows, 0 <= col < cols.

Документация

Wikipedia: Off-by-one error.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам