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.

[birdwatcher]

Баг только один: вместо использования поиска из стандартной библиотеки слеплено нечто любительское на коленке.

[aklepatc]

Это тоже по-своему верно.

Мне, однако кажется, что реалистичные ситуации, где нужен самопальный метод половинного деления таки случаются в жизни. Правда, это, скорее всего, будет не в Го.

[nponeccop]

> реалистичные ситуации, где нужен самопальный метод половинного деления
> таки случаются в жизни

А давайте мы их придумаем.

Как насчёт Range Minimal Query, Segment Trees и Fenwick Trees? Есть либы?

[aklepatc]

Спасибо за поддержку!

Но, вообще-то мне в этом месте надо сознаваться в недостатке базового образования (или проще говоря в дремучем невежестве ; ) и лезть в Гугл.

Ну или задавать мета-вопросы типа "откуда вы всё это знаете"?

Попробую про эти вещи хотя бы в первом приближении почитать...

[ext_3948950]

Эм... Берём массив [10, 20], ищем 10 (которое там есть, кстати):
l := 0 - OK, пока что l - это 0
r := len(arr) - 1 - OK, пока что r - это 1
for l < r { - у нас l=0, r=1, 0 < 1, так что условие выполнено, входим в цикл.
m := (l + r) / 2 - OK, у нас m - это (0 + 1)/2 = 1/2 = 0 (целочисленное деление).
if target < arr[m] { - OK, у нас target - это 10, arr[m] = arr[0] = 10 - они равны, так что условие не выполнено, идём в else
l = m - хорошо, у нас l было 0, и m было тем же самым, так что l остаётся прежним.
Цикл закончился, переходим на начало, и обнаруживаем, что не изменилось вообще ничего. Поэтому цикл повторяется вечно.

[aklepatc]

Да, что-то такое...
Мы это там выше обсуждали вдоль и поперёк. Я уже, честно говоря, позабыл подробности.

[ext_3948950]

А, да, не заметил сразу.