Pull to refresh

Только 10% программистов способны написать двоичный поиск

Reading time 2 min
Views 83K
Дональд Кнут (известный тем, что его книги никто не читает) пишет, что хотя первый двоичный поиск был опубликован в 1946 году, первый двоичный поиск без багов был опубликован только в 1962.

Алгоритм двоичного поиска похож на то, как мы ищем слово в словаре. Открываем словарь посередине, смотрим в какой из половин будет нужное нам слово. Допустим, в первой. Открываем первую часть посередине, продолжаем половинить, пока не найдем нужное слово.

С массивами так: есть упорядоченный массив, берем число из середины массива, сравниваем с искомым. Если оно оказалось больше, значит искомое число в первой половине массива, если меньше — во второй. Продолжаем делить оставшуюся половину, когда находим нужное число возвращаем его индекс, если не находим возвращаем null.


В статье утверждалось, что только 10% программистов могут решить эту задачу. Да не может быть! Вот лохи, подумал я, зарядил Firebug, каких-то 5 минут и… нерабочая версия готова. Еще одна итерация, и еще, и еще. В сумме полтора часа, и в конечном решении все равно 2 ошибки. Стыдно как!

Если вы никогда не писали двоичный поиск, я предлагаю вам написать этот алгоритм на любимом языке и выложить его в комменты без тестирования. Любой хороший программист сходу напишет этот поистине детский алгоритм. Потратьте столько времени, сколько нужно. В комменте укажите язык, затраченное время, и ссылку на ваш труд на pastie.org.

На Википедии правильное решение.

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

Спойлер.
Распространенные ошибки:
— не работает с массивом из 0/1/2 элементов
— не находит первый или последний элемент
— некорректно работает, если элемента в массиве нет
— некорректно работает, если в массиве есть повторяющиеся элементы
— обращение к элементами за пределами массива
— козырная, которая была в JDK, переполнение целого при вычислении среднего индекса

P.S.
Кто-то скажет, что эта функция уже есть в стандартной библиотеке.
Это так, согласен. Но это не значит, что от решения таких задач нет толку. Смотрите, если все простые задачи уже решены за нас в стандартной библиотеке, значит нам остались только более сложные задачи, которых там нет. Как мы будем решать эти более сложные задачи, если мы не умеем решить даже простую задачу из стандартной библиотеки?

Я вам скажу как. Очень плохо. Я делал проверку кода, когда работал в команде. Многие программисты не могли родить простейший код даже с 20 попытки! Они привыкли сидеть на готовом, и не способны написать что-то сложнее композиции foo(bar()), а если и напишут, то реализация будет медленная, путанная, и с ошибками.
Tags:
Hubs:
+115
Comments 538
Comments Comments 538

Articles