Какая алгоритмическая сложность бинарного поиска

Что проверяют

Базовое понимание асимптотики и то, как она проявляется в .NET: что даёт стандартная библиотека и как читать её результат. Следом обычно просят написать поиск руками или спрашивают, почему Array.BinarySearch вернул отрицательное число, отличное от -1.

Как отвечать

• время: O(log n), потому что каждая итерация отбрасывает половину диапазона. На миллионе элементов это не больше 20 сравнений, на миллиарде около 30;
• память: O(1) в итеративной реализации, O(log n) стека в рекурсивной. Хвостовые вызовы в C# не гарантированы, поэтому в продакшене пишут цикл;
• предусловие: массив отсортирован тем же компаратором, которым вы ищете. Иначе результат не определён, а исключения не будет.

Готовые методы: Array.BinarySearch, List<T>.BinarySearch, а для Span<T> и ReadOnlySpan<T> расширение BinarySearch из MemoryExtensions. Если элемент найден, они возвращают его индекс. Если нет, отрицательное число: побитовое дополнение индекса первого большего элемента. Отсюда идиома:

int i = Array.BinarySearch(arr, x); if (i < 0) i = ~i;

После неё i указывает место, куда вставить x, чтобы массив остался отсортированным.

Для своих типов передают IComparer<T> или реализуют IComparable<T>. Строки ищите с тем же StringComparer, что использовался при сортировке, иначе культурное и ординальное сравнение разойдутся.

Середину считайте как lo + ((hi-lo) >> 1). Выражение (lo+hi)/2 в непроверяемом контексте молча переполнится на больших индексах, и вы получите отрицательный индекс.

Сравнение с коллекциями уместно в конце: SortedList<TKey,TValue> ищет ключ бинарным поиском, SortedDictionary держит красно-чёрное дерево, оба дают O(log n).

Где спотыкаются

Проверяют результат через == -1. Ровно -1 при промахе метод вернёт, только если элемент меньше всех, поэтому правильная проверка < 0.

Используют LINQ Contains или First на отсортированном массиве и называют это поиском. Это линейный перебор O(n), сортировка ему никак не помогает.

Путают границы цикла: while (lo < hi) вместе с hi = mid-1 пропускает элемент, а lo = mid без +1 зацикливается на двух элементах.