Practicing Our Craft

[aklepatc]

Find two bugs in the following binary search implementation:
func search(arr []int, target int) int {
l := 0
r := len(arr) - 1
for l < r {
m := (l + r) / 2
if target < arr[m] {
r = m - 1
} else {
l = m
}
}
if arr[l] == target { //assume len(arr) != 0
return l
}
return -1
}None of this is Golang specific. If you know Java, C or

Comments

[morfizm]

Я больше, чем два бага нашёл (впрочем, можно 1 и 3 считать одним багом):

1. На массиве длиной в 0 сходу будет access violation in line "if arr[l] == target"
2. На практике маловероятно, но, в принципе, в "m := (l + r) / 2" может быть int overflow. По уму надо делать что-то вроде m := l/2 + r/2 + (l%2 + r%2)/2
3. "r = m - 1" может привести к "r < 0", когда число не нашлось, и у нас снова будет access violation in line "if arr[l] == target"

Хороший паттерн (не супер оптимальный по числу сравнений, зато безопасный) - это внутри цикла сделать тройной if, в котором будет проверка на равенство и early return, а за циклом unconditionally return -1.
Второй вариант - в условие после цикла добавить проверку границ: "if (l <= r) && (arr[l] == target)" (можно написать "if (r >= 0) && (arr[l] == target)", что чуть более эффективно, но это будет менее читаемо, так что я бы не стал

[morfizm]

Upd.: я тут подумал, конечно, в п.3. access violation не будет, ведь arr[l] это корректный адрес, хоть и за пределами рассматриваемого диапазона. Мало того, если бы arr[l] содержал искомое число, то мы бы не попали в эту ситуацию, а, значит, он его не содержит (ну, или массив не отсортирован, но тогда у нас и так, и так был бы undefined behavior). Таким образом, в случае п.3. бага не будет, будет просто некорректный statement, который "работает правильно по голой случайности". Что противно, но формально не доебёшься и не скажешь, что это баг. Таким образом, настоящих бага я нашёл всего два.

[aklepatc]

1 - строго говоря, правильно. Однако эта проверка убрана для упрощения кода. Мне, видимо, надо дописать "предполагаем, что длина ненулевая".
2 - верно описана проблема/баг. Предложенная "альтернативная формула" мне с первого взгляда кажется неверной.
3 - мне кажется, что это не проблема. Отрицательное r вызовет завершение цикла. А ниже мы смотрим только на l. Извини (посмотрел твой update): мы, кажется, одинаково понимаем этот пункт.

Про всё остальное. Спасибо за подробный разбор! Я вечером "врублюсь" и отпишу по всем пунктам. Пока что это так "на бегу".

[morfizm]

О, т.е. ты хочешь сказать, там есть ещё один баг, который я не увидел?

Фак! Увидел. Конечно, вместо "l = m" надо "l = m + 1". Лень придумывать пример, на котором получится вечный цикл, но уверен, что его можно построить.

Вернее, не так: надо и "l = m + 1", и отдельную проверку на точное равенство.
Без трёхстороннего if-а не обойтись.

Но я бы не допустил этот баг, т.к. всегда херачу трёхсторонний if в имплементации binary search.

[aklepatc]

Прямо в точку!

Я бы, правда, чинил этот баг немного по-другому, но это уже скорее дело вкуса.

Твой способ мне тоже нравится! Он явно пуленепробиваемый. На собеседовании это важнее, чем вкусовщина.

[aklepatc]

2. Мне кажется, что правильная формула такая: m := l + (r - l) / 2.

[rezkiy]

std::midpoint

[aklepatc]

Классно! Даже не знал, что такое есть. Давно на плюсах не пишу...

[aklepatc]

Со всем остальным согласен на 100%. Ещё раз большое спасибо за подробный разбор!

Особенно зашло предложение не включать правый конец. Я вырос на C++. Там в STL везде так сделано.