Алгоритмы C/C++

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

После каждого сравнения отбрасывается половина диапазона.

Что такое Двоичный поиск?

После каждого сравнения отбрасывается половина диапазона.

Ищите в отсортированных данных за логарифмическое время.

Важные моменты

Проверяйте пустые, одиночные, повторяющиеся и отсортированные данные.
Отделяйте корректность от оптимизации.
В production предпочитайте стандартную библиотеку.

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

O(log n)

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

Примеры кода на 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++

Вход должен быть sorted. Цикл C и std::lower_bound выполняются за O(log n) на random-access диапазоне.

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

C++

Итераторы и алгоритмы отделяют операцию от хранения.

Практические задания

Запустите обе версии и изменяйте их, сравнивая гарантии языков.

Проследите каждое сравнение.
Проверьте дубликаты и крайние значения.
Сравните со стандартной библиотекой.