O(log n) или O(n)? Разбор алгоритмов поиска для собеседований и практики
Привет, Хабр! В 2006 году Джошуа Блох, автор «Effective Java» и один из создателей Java Collections Framework, опубликовал разбор бага в бинарном поиске JDK, который сидел в коде почти десять лет. Проблема оказалась в вычислении среднего индекса: (left + right) / 2 переполнялось на больших массивах. Бинарный поиск — один из первых алгоритмов, которые учат на курсах, и всё равно ошибка пряталась в стандартной библиотеке.
На собеседованиях задачи на поиск спрашивают постоянно. В продакшене разница между O(n) и O(log n) — это разница между секундами и миллисекундами на десяти миллионах записей.


