Comments 2
Уже где-то писал, что в бинарном поиске (который "обычный") среднее количество итераций будет почти как как максимальное, log(n). То есть lowerBound и upperBound требуют в среднем в два раза меньше сравнений, поэтому обычный поиск лучше сделать через один из них, а не писать отдельно.
Вот после такого собеседования, получаем разработчиков, код которых занимается сортировками многомиллионных массивов, вместо использования старого доброго BTree.
Sign up to leave a comment.
O(log n) или O(n)? Разбор алгоритмов поиска для собеседований и практики