Я ищу один алгоритм или структуру данных, которая настолько неизвестна, но при этом полезна, что вы считаете это ужасным надзором со стороны сообщества информатики или программирования. Если бы мы могли все это изучить, многое было бы сделано для многих будущих программ.
Самый лучший, который я могу придумать, - это интерполяционный поиск, который знает только очень немногие программисты, тогда как все знают бинарный поиск. Я думаю, что нет никаких сомнений в том, что быстрый поиск упорядоченного списка - довольно полезный и фундаментальный алгоритм.
Оба почти идентичны реализации - так что это не проблема.
Он выполняет O (log (log (n))) на равномерно распределенных данных по сравнению с двоичными поисками O (log (n)). Это означает, что поиск 4 миллиардов номеров требует только 5 пробников против 32, что намного лучше!
По не идеально однородным данным, он по-прежнему очень хорошо работает большую часть времени. Только когда данные действительно искажены, это так же плохо, как бинарный поиск или хуже. Это O (n) наихудший случай, когда данные сильно искажены, но это довольно редко встречается в большинстве реальных ситуаций.
Еще можно построить четный/нечетный алгоритм для чередования между ними и получить наихудший случай двоичного поиска со средним случаем интерполяционного поиска для смягчения экстремальных ситуаций.
На самом деле нет веских оснований, которые так упускают из виду большинство программистов/библиотек.
Может ли кто-нибудь еще победить это?
