Учебная версия на русском. Код и его вывод сохранены в исходном виде.

Двоичный поиск на C

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

Двоичный поиск требует отсортированного массива. Сравните цель со средним элементом. Если цель меньше, исключите правую половину; если больше — левую. При совпадении верните индекс.

Вычисляйте середину как low + (high - low) / 2, чтобы не складывать два больших индекса. При изменении границ исключайте уже проверенную середину. Когда low становится больше high, значение отсутствует.

Итеративный вариант занимает O(log N) времени и O(1) дополнительной памяти. Проверьте крайние элементы, отсутствующую цель и массив из одного элемента. При дубликатах результат не обязательно указывает на первое вхождение.

Код C

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        // Prevent (low + high) integer overflow
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1; // Target not found
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 23;
    int result = binarySearch(arr, n, target);

    if (result != -1)
        printf("Element %d found at index %d\n", target, result);
    else
        printf("Element %d not present\n", target);

    return 0;
}

Открыть в компиляторе

Ожидаемый вывод

Element 23 found at index 5

Частые вопросы

Почему код и вывод остаются на английском?

Ключевые слова, идентификаторы и строки, проверяемые тестами, сохранены, чтобы не менять программу. Объяснения и элементы управления переведены.