Бинарный поиск — классический алгоритм. На вход алгоритм принимает отсортированный массив чисел и число для поиска. На выходе — индекс этого числа в массиве.

Алгоритмически это выглядит так:

1. Запоминаем левую L и правую R границы массива (индексы, а не значения)
2. Берем индекс M посередине между L и R
3. Если значение массива по индексу M меньше нужного — L меняем на M, если больше — R меняем на M
4. Возвращаемся на шаг 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