Бинарный поиск в C#
Бинарный поиск — классический алгоритм. На вход алгоритм принимает отсортированный массив чисел и число для поиска. На выходе — индекс этого числа в массиве.
Алгоритмически это выглядит так:
- Запоминаем левую L и правую R границы массива (индексы, а не значения)
- Берем индекс M посередине между L и R
- Если значение массива по индексу M меньше нужного — L меняем на M, если больше — R меняем на M
- Возвращаемся на шаг 2
Таким образом мы на каждом шаге алгоритма сужаем область поиска в 2 раза. Этот алгоритм имеет сложность O(log(n)).
В теории все просто, но на практике возникают проблемы.
Приведу сразу свою реализацию, а потом разберем все проблемы.
public static int Search<T>(T[] data, T value) where T : IComparable { var left = data.GetLowerBound(0); var right = data.GetUpperBound(0); if (left == right) return left; while (true) { if (right - left == 1) { if (data[left].CompareTo(value) == 0) return left; if (data[right].CompareTo(value) == 0) return right; return -1; } else { var middle = left + (right - left) / 2; var comparisonResult = data[middle].CompareTo(value); if (comparisonResult == 0) return middle; if (comparisonResult < 0) left = middle; if (comparisonResult > 0) right = middle; } } }
Распространенная ошибка реализации — переполнение типа при вычислении середины интервала. Именно поэтому середина вычисляется так
var middle = left + (right - left) / 2;
А не так
var middle = (left + right) / 2;
Еще одна проблема — выход из алгоритма. Нужно правильно обрабатывать ситуацию, когда интервал поиска свелся к двум соседним индексам. Я для наглядности вместо хитрых операций с индексами вынес эту ситуацию в отдельный блок кода
if (right - left == 1) { if (data[left].CompareTo(value) == 0) return left; if (data[right].CompareTo(value) == 0) return right; return -1; }
Так же можно добавить дополнительную оптимизацию для ситуации, когда value заведомо слишком маленькое или большое. Будут такие проверки в начале метода:
if (value < data[left] || value > data[right]) return -1;
Рабочий код как всегда лежит на гитхабе
В реальном проекте рекомендую использовать List.BinarySearch