O(log n) или O(n)? Разбор алгоритмов поиска для собеседований и практики

[Alexandroppolus]

Уже где-то писал, что в бинарном поиске (который "обычный") среднее количество итераций будет почти как как максимальное, log(n). То есть lowerBound и upperBound требуют в среднем в два раза меньше сравнений, поэтому обычный поиск лучше сделать через один из них, а не писать отдельно.

[ptr128]

Вот после такого собеседования, получаем разработчиков, код которых занимается сортировками многомиллионных массивов, вместо использования старого доброго BTree.