CodeUtility
Кодить проще - жить легче!
Алгоритмы C/C++

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

В этом уроке вы будете искать в отсортированном массиве за O(log n): с помощью цикла, написанного вручную на C, и std::lower_bound в C++.

Введение

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

Главное

  • Проверяйте на пустом вводе, одном элементе, повторах и уже отсортированных данных.
  • Сначала добейтесь правильной работы кода, а потом оптимизируйте.
  • В реальном коде отдавайте предпочтение готовым функциям стандартной библиотеки.

Визуализация: Двоичный поиск в C и C++

O(log n)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Примеры кода на C и C++

C
Запустить →
main.c
#include <stdio.h>

int search(const int *values, int size, int target) {
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        int middle = low + (high - low) / 2;
        if (values[middle] == target) return middle;
        if (values[middle] < target) low = middle + 1;
        else high = middle - 1;
    }
    return -1;
}

int main(void) {
    int values[] = {3, 7, 11, 16, 23, 28};
    printf("index=%d\n", search(values, 6, 23));
}
Результат выполнения
index=4
C++
Запустить →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{3, 7, 11, 16, 23, 28};
    auto match = std::lower_bound(values.begin(), values.end(), 23);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}
Результат выполнения
index=4

Сравнение C и C++

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

C

Циклы, указатели, длины и временные буферы пишутся явно.

C++

Итераторы и стандартные алгоритмы отделяют обработку от способа хранения данных.

Упражнения для практики

Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.

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

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи