// Búsqueda binaria sobre un rango semiabierto [lo, hi), y dos versiones que fallan.
#ifndef SEARCH_H
#define SEARCH_H

#include <cassert>
#include <ostream>
#include <vector>

// Devuelve el primer índice i con a[i] >= x, o a.size() si no hay ninguno.
// Requiere que a esté ordenado de menor a mayor.
// Invariante: todo a[i] con i < lo es menor que x, y todo a[i] con i >= hi es mayor o igual que x.
inline int first_at_least(const std::vector<int>& a, int x) {
    int lo = 0;
    int hi = static_cast<int>(a.size());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

// La misma búsqueda, comprobando en cada vuelta la invariante entera y que hi - lo baja.
// Si recibe un flujo, escribe una línea por vuelta.
inline int first_at_least_checked(const std::vector<int>& a, int x, std::ostream* log) {
    const int n = static_cast<int>(a.size());
    int lo = 0;
    int hi = n;
    auto check = [&] {
        assert(0 <= lo && lo <= hi && hi <= n);
        for (int i = 0; i < lo; i++) assert(a[i] < x);
        for (int i = hi; i < n; i++) assert(a[i] >= x);
    };
    check();
    while (lo < hi) {
        int size_before = hi - lo;
        int mid = lo + (hi - lo) / 2;
        if (log) *log << lo << ' ' << hi << ' ' << mid << ' ' << a[mid] << '\n';
        if (a[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
        check();
        assert(hi - lo < size_before);
    }
    assert(lo == hi);
    return lo;
}

// Mal: conserva "todo a[i] con i < lo es menor que x", termina, y aun así no da el resultado.
inline int search_weak_invariant(const std::vector<int>& a, int x) {
    int lo = 0;
    int hi = static_cast<int>(a.size());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) {
            lo = mid + 1;
        } else {
            hi = lo;
        }
    }
    return lo;
}

// Mal: con lo = mid, el rango puede dejar de achicarse. Devuelve -1 si se pasa de max_steps,
// para que el ejemplo no se quede colgado.
inline int search_lo_is_mid(const std::vector<int>& a, int x, int max_steps) {
    int lo = 0;
    int hi = static_cast<int>(a.size());
    for (int step = 0; lo < hi; step++) {
        if (step == max_steps) return -1;
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    return lo;
}

#endif