Реализован ли в .NET поиск по отсортированным массивам?

Есть ли информация о работе C# с коллекциями массивами и тд в плане реализации? Ну, то есть поиск по сортированному массиву примерно в 2 раза быстрее, чем по несортированному. А как происходит поиск в Array, List, Dictionary и тд?
Для примера вот задачка. Есть класс аэропорт(название, координаты). Есть класс коллекция аэропортов. В коллекции есть List<аэропорт>, как хранилище объектов аэропорт. В коллекции не может быть 2 аэропорта с одинаковым названием или с одинаковыми координатами. Что быстрее, использовать list.Find(predicate) или добавить к классу коллекции два словаря:
Dictionary<строка, аэропорт>
Dictionary<координаты, аэропорт>
и искать совпадения по этим коллекциям? Если со словарями поиск будет быстрее, то на сколько?

Ответ

В .NET 4.5 и выше есть метод List(T).BinarySearch, который использует алгоритм двоичного поиска. Двоичный поиск намного быстрее, чем простой итеративный поиск.
Вот пример:
var ints = new List { 1, 56, 112 }; ints.BinarySearch(1); // 0 ints.BinarySearch(56); // 1 ints.BinarySearch(112); // 2 ints.BinarySearch(0); // -1 ints.BinarySearch(10); // -2 ints.BinarySearch(100); // -3 ints.BinarySearch(200); // -4
Для List<аэропорт>, в принципе это тоже возможно, но надо создать IComparer для аэропортов.
Что быстрее, использовать list.Find(predicate) или добавить к классу коллекции два словаря?
Для больших коллекцией быстрее использовать словари.
Согласно документации, временная сложность метода Dictionary.ContainsKey приближается O(1). Временная сложность метода List.BinarySearch - O(log(n)), и временная сложность метода List.Find - O(n)