Как работает бинарный поиск? Что принимает функция и какова сложность?

Алгоритмическая сложность бинарного поиска в отсортированном массиве — O(log n), где n — количество элементов в массиве.

Это означает, что с каждым шагом поиска размер рассматриваемой части массива уменьшается вдвое, что обеспечивает очень быструю работу даже на больших данных.

Пример бинарного поиска на C#:

int BinarySearch(int[] arr, int target) {
    int left = 0, right = arr.Length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // элемент не найден
}