Приведи пример реализации алгоритма бинарного поиска в отсортированном массиве.

Бинарный поиск — это алгоритм поиска элемента в отсортированном массиве за время O(log n). Принцип работы: на каждом шаге интервал поиска делится пополам, пока элемент не будет найден или интервал не станет пустым.

Реализация на C# (итеративный подход):

public static int BinarySearch(int[] sortedArray, int target)
{
    // Границы текущего интервала поиска
    int left = 0;
    int right = sortedArray.Length - 1;

    while (left <= right)
    {
        // Вычисление середины с защитой от переполнения
        int mid = left + (right - left) / 2;

        if (sortedArray[mid] == target)
        {
            return mid; // Элемент найден
        }
        else if (sortedArray[mid] < target)
        {
            // Искомый элемент в правой половине
            left = mid + 1;
        }
        else
        {
            // Искомый элемент в левой половине
            right = mid - 1;
        }
    }
    // Элемент не найден
    return -1;
}

Объяснение ключевых моментов:

1. Условие left <= right: Позволяет обрабатывать интервалы, включая случаи с одним элементом.
2. Расчёт mid: Используется формула left + (right - left) / 2 вместо (left + right) / 2 для избежания потенциального переполнения при очень больших значениях left и right.
3. Сдвиг границ: В зависимости от сравнения, мы отбрасываем заведомо неподходящую половину массива.

Пример использования:

int[] data = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
int index = BinarySearch(data, 23); // index = 5
int notFound = BinarySearch(data, 50); // notFound = -1

Для работы с любыми типами можно использовать обобщённую версию с IComparable<T>:

public static int BinarySearch<T>(T[] sortedArray, T target) where T : IComparable<T>
{
    int left = 0, right = sortedArray.Length - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        int comparison = sortedArray[mid].CompareTo(target);
        if (comparison == 0) return mid;
        if (comparison < 0) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}