JuniorКодОчень частоЕщё не отвечали

Реализуйте бинарный поиск в массиве

Реализуйте бинарный поиск в отсортированном по возрастанию массиве. Верните индекс target или -1, если его нет.

Требования:

O(log n) время, O(1) дополнительной памяти.
Вычисляйте середину как low + (high - low) / 2, чтобы избежать переполнения.
Корректно задайте границу цикла; обработайте пустой массив.
Не используйте std::binary_search или std::lower_bound.

int binarySearch(const std::vector<int>& arr, int target) {
    // ваш код здесь
}

Допишите реализацию.

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

✗Переполнение целого в mid = (low + high) / 2 при больших low и high — используйте low + (high - low) / 2
✗Ошибка на единицу в условии цикла: while (low < high) vs while (low <= high) меняет семантику
✗Не проверять, что массив отсортирован — бинарный поиск на несортированных данных даёт неверный результат

→Чем std::lower_bound отличается от std::binary_search?
→Как расширить бинарный поиск для нахождения самого левого / самого правого вхождения значения?

Оглавление

Задача

Реализуйте бинарный поиск значения в отсортированном массиве целых чисел. Верните индекс элемента или -1, если элемент не найден.

Решение

#include <vector>
#include <cassert>

// Итеративный бинарный поиск — O(log n), O(1) памяти
int binarySearch(const std::vector<int>& arr, int target) {
    int low  = 0;
    int high = static_cast<int>(arr.size()) - 1;

    while (low <= high) {
        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;
}

// Рекурсивный вариант (для иллюстрации)
int binarySearchRec(const std::vector<int>& arr, int target, int low, int high) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)  return binarySearchRec(arr, target, mid + 1, high);
    return                         binarySearchRec(arr, target, low, mid - 1);
}

int main() {
    std::vector<int> v = {1, 3, 5, 7, 9, 11, 13};

    assert(binarySearch(v, 7)  == 3);
    assert(binarySearch(v, 1)  == 0);
    assert(binarySearch(v, 13) == 6);
    assert(binarySearch(v, 4)  == -1);
    assert(binarySearch({}, 1) == -1);
}

Ключевые моменты

Используйте mid = low + (high - low) / 2, а не (low + high) / 2, чтобы избежать переполнения.
Инвариант цикла: low <= high означает «может существовать ненайденный элемент в диапазоне».
std::lower_bound из <algorithm> делает то же самое, но возвращает итератор на первый элемент ≥ target.

Открыть тему в роадмапе →

Оглавление

Реализуйте бинарный поиск в массиве

Реализуйте бинарный поиск в отсортированном по возрастанию массиве. Верните индекс target или -1, если его нет.

Требования:

O(log n) время, O(1) дополнительной памяти.
Вычисляйте середину как low + (high - low) / 2, чтобы избежать переполнения.
Корректно задайте границу цикла; обработайте пустой массив.
Не используйте std::binary_search или std::lower_bound.

int binarySearch(const std::vector<int>& arr, int target) {
    // ваш код здесь
}

Допишите реализацию.

Решение

#include <vector> #include <cassert> // Итеративный бинарный поиск — O(log n), O(1) памяти int binarySearch(const std::vector<int>& arr, int target) { int low = 0; int high = static_cast<int>(arr.size()) - 1; while (low <= high) { 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; } // Рекурсивный вариант (для иллюстрации) int binarySearchRec(const std::vector<int>& arr, int target, int low, int high) { if (low > high) return -1; int mid = low + (high - low) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) return binarySearchRec(arr, target, mid + 1, high); return binarySearchRec(arr, target, low, mid - 1); } int main() { std::vector<int> v = {1, 3, 5, 7, 9, 11, 13}; assert(binarySearch(v, 7) == 3); assert(binarySearch(v, 1) == 0); assert(binarySearch(v, 13) == 6); assert(binarySearch(v, 4) == -1); assert(binarySearch({}, 1) == -1); }

Ключевые моменты

Используйте mid = low + (high - low) / 2, а не (low + high) / 2, чтобы избежать переполнения.

Инвариант цикла: low <= high означает «может существовать ненайденный элемент в диапазоне».

std::lower_bound из <algorithm> делает то же самое, но возвращает итератор на первый элемент ≥ target.