Skip to content

🔍 Двоично Търсене (Binary Search)

Двоичното търсене е един от най-фундаменталните и ефективни алгоритми. То позволява намирането на елемент в сортиран масив за логаритмично време \(O(\log N)\), вместо линейно \(O(N)\).

1. Класически Алгоритъм

Идеята е да поддържаме интервал [L, R], в който търсеният елемент може да се намира. На всяка стъпка проверяваме средата mid. * Ако arr[mid] == target, намерили сме го. * Ако arr[mid] < target, търсим в дясната половина [mid + 1, R]. * Ако arr[mid] > target, търсим в лявата половина [L, mid - 1].

int binarySearch(const vector<int>& arr, int target) {
    int l = 0, r = arr.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2; // Предпазва от overflow при (l+r)
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1; // Не е намерен
}

2. STL Функции (lower_bound / upper_bound)

В C++ рядко пишем чист binary search, освен ако условието не е специфично. Библиотеката <algorithm> предоставя:

  • lower_bound(begin, end, val): Връща итератор към първия елемент, който е \(\ge val\).
  • upper_bound(begin, end, val): Връща итератор към първия елемент, който е \(> val\).
vector<int> v = {10, 20, 20, 20, 30};

// Първото 20
auto lb = lower_bound(v.begin(), v.end(), 20); 
cout << (lb - v.begin()); // Индекс 1

// Първото > 20 (т.е. 30)
auto ub = upper_bound(v.begin(), v.end(), 20); 
cout << (ub - v.begin()); // Индекс 4

// Брой срещания на 20
cout << (ub - lb); // 3

3. Двоично Търсене по Отговор (Binary Search on Answer)

Това е най-мощното приложение на алгоритъма в състезания. Използва се, когато търсим "минималната стойност \(X\), за която е възможно да изпълним условие \(P(X)\)" (или максималната). Функцията \(P(X)\) трябва да е монотонна: * Ако е възможно за \(X\), то е възможно и за всяко \(Y > X\) (или обратното).

Шаблон: 

bool check(long long x) {
    // Възможно ли е да се справим със стойност x?
    // Greedy проверка или симулация O(N)
    return true/false;
}

long long solve() {
    long long l = 0, r = 1e18; // Пространство на търсене
    long long ans = -1;

    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1; // Търсим по-малко (за минимум)
            // l = mid + 1; // За максимум
        } else {
            l = mid + 1; // Трябва по-голямо
            // r = mid - 1; // За максимум
        }
    }
    return ans;
}

Примерни задачи:

  • "Aggressive Cows" (SPOJ): Минималното разстояние между крави да е максимално.
  • "K-th Number": Намиране на k-тото число в сложна структура.

4. Двоично търсене върху реални числа

Когато отговорът е дробно число (double), вместо l <= r използваме фиксиран брой итерации. Това е по-стабилно от while (r - l > EPS) заради проблемите с точността.

double l = 0, r = 1e9;
for (int i = 0; i < 100; i++) { // 100 итерации дават огромна точност
    double mid = (l + r) / 2;
    if (check(mid)) r = mid;
    else l = mid;
}

Използва се за намиране на максимум/минимум на унимодална функция (функция, която расте и после намалява, или обратно - има само един екстремум).

Разделяме интервала на 3 части с две точки \(m_1\) и \(m_2\): \(m_1 = l + (r-l)/3\) \(m_2 = r - (r-l)/3\)

  • Ако \(f(m_1) < f(m_2)\): Максимумът е надясно, местим \(L = m_1\).
  • Ако \(f(m_1) > f(m_2)\): Максимумът е наляво, местим \(R = m_2\).

6. Задачи

  1. Codeforces 706B: Interesting drink (upper_bound).
  2. SPOJ EKO: Класически BS по отговор.
  3. LeetCode 33: Search in Rotated Sorted Array.

🏁 Заключение

Ако видите "монотонност" или думата "максимизирай минимума", веднага мислете за Binary Search.

7. Още примери за двоично търсене по отговор

7.1. Задача: Разделяне на масив

Условие: Имате масив с \(N\) числа. Трябва да го разделите на \(K\) непразни непрекъснати части така, че максималната сума в една част да е минимална. Намерете тази минимална стойност.

Решение: Двоично търсене по отговора. * \(L = \max(arr)\) (поне едно число трябва да е в някоя част). * \(R = \sum(arr)\) (всичко в една част). * check(x): Можем ли да разделим масива така, че никоя част да няма сума \(> x\)?

bool check(vector<int>& arr, int k, long long maxSum) {
    int parts = 1;
    long long currentSum = 0;

    for (int num : arr) {
        if (num > maxSum) return false; // Невъзможно
        if (currentSum + num > maxSum) {
            parts++;
            currentSum = num;
        } else {
            currentSum += num;
        }
    }

    return parts <= k;
}

long long solve(vector<int>& arr, int k) {
    long long l = *max_element(arr.begin(), arr.end());
    long long r = accumulate(arr.begin(), arr.end(), 0LL);
    long long ans = r;

    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (check(arr, k, mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

7.2. Задача: Копиране на книги

\(N\) книги с различна дебелина. \(K\) работници трябва да ги копират. Всеки работник взема непрекъснат блок от книги. Минимизирайте максималното време, което изразходва един работник.

Решението е идентично с предишната задача - двоично търсене по времето.

8. Бинарно търсене върху дробни числа - още примери

8.1. Задача: Минимално време за изпълнение

\(N\) машини, всяка изпълнява задача за \(t_i\) секунди. Трябва да изпълним \(M\) задачи. Какво е минималното време?

Решение: Двоично търсене по време. * \(L = 0\), \(R = \max(t_i) \times M\) (една машина прави всичко). * check(T): За време \(T\), колко задачи може да свършим? \(\sum_{i} \lfloor T / t_i \rfloor \ge M\)?

bool canFinish(vector<int>& times, long long M, long long T) {
    long long totalTasks = 0;
    for (int t : times) {
        totalTasks += T / t;
        if (totalTasks >= M) return true; // Оптимизация за избягване на overflow
    }
    return totalTasks >= M;
}

long long minTime(vector<int>& times, long long M) {
    long long l = 0, r = 1e18;
    long long ans = r;

    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (canFinish(times, M, mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

9.1. Безкраен цикъл

Ако обновявате границите грешно (напр. l = mid вместо l = mid + 1), циклят може да стане безкраен.

Решение: Винаги използвайте mid = l + (r - l) / 2 и l = mid + 1 или r = mid - 1.

9.2. Overflow при (l + r) / 2

За големи стойности, l + r може да надвиши границата на int или дори long long.

Решение: Използвайте mid = l + (r - l) / 2.

9.3. Грешна функция check

Уверете се, че функцията check действително е монотонна. Ако не е, binary search няма да работи коректно.

🏁 Обобщение

Двоичното търсене е изключително мощна техника с широко приложение. Основните му форми са: * Класическо търсене в сортиран масив. * Търсене по отговор за оптимизационни задачи. * Троично търсене за унимодални функции.

Винаги когато видите монотонна функция или проблем от типа "намерете максималната минимална стойност", помислете за binary search!