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

Двоичный поиск в отсортированном массиве

Найдите индекс цели за логарифмическое время или сообщите об отсутствии.

Прочитайте N и цель K, затем N целых в неубывающем порядке. Функция binary_search должна вернуть индекс с нуля при совпадении либо -1, если K отсутствует.

Вычисляйте mid = low + (high - low) / 2 и исключайте половину, где цели быть не может. Сохраняйте английские метки Found at index: и Not found: -1.

Ввод

Первая строка: N и K. Вторая: N упорядоченных целых через пробел.

Вывод

Found at index: <индекс> либо Not found: -1

Ограничения

1 <= N <= 100 000
-1 000 000 000 <= arr[i], K <= 1 000 000 000
Массив упорядочен по неубыванию.
Поиск: O(log N) времени и O(1) дополнительной памяти.

Подсказки

Начните с low = 0 и high = n - 1; продолжайте при low <= high.
Исключайте середину: high = mid - 1 или low = mid + 1.

Код C

#include <stdio.h>

// Function to perform binary search
// Returns 0-based index of target if found, else -1
int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    // TODO: Implement O(log N) binary search loop
    // Tip: Use mid = low + (high - low) / 2 to prevent integer overflow

    return -1; // Target not found
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

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

Решение и объяснение

При совпадении arr[mid] верните mid. Меньшая цель может находиться только слева, большая — только справа.

Каждый шаг примерно вдвое уменьшает диапазон. Когда границы пересеклись, цели нет. Проверьте крайние элементы и отсутствующее значение.

Сам поиск занимает O(log N), но чтение N входных чисел — O(N). При дубликатах возвращается одно вхождение, не обязательно первое.

Код решения

#include <stdio.h>

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

    while (low <= high) {
        // Overflow-safe midpoint calculation
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

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

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

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