Как избегать 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--) {}Binary search
Есть два популярных стиля.
Закрытый интервал [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.