binary_search.cpp

#include <cstdint>
#include <cassert>
#include <vector>

static constexpr int INF = 1'000'000'007;
using i32 = std::int32_t;

using namespace std;

i32 LowerBound(const vector<i32>& nums, const i32 key) {
    i32 lo = 0;
    i32 hi = nums.size() - 1;
    i32 ans = -1;
    while (lo <= hi) {
        const i32 mi = lo + (hi - lo) / 2;
        if (nums[mi] < key) {
            lo = mi + 1;
        } else {
            ans = mi;
            hi = mi - 1;
        }
    }
    return ans;
}

i32 LowerBoundRec(const vector<i32>& nums, i32 key, i32 lo = -1, i32 hi = -1) {
    if (lo > hi) return INF;
    if (lo == -1) lo = 0;
    if (hi == -1) hi = size(nums) - 1;
    const i32 mi = lo + (hi - lo) / 2;
    if (nums[mi] < key) return LowerBoundRec(nums, key, mi + 1, hi);
    return min(mi, LowerBoundRec(nums, key, lo, mi - 1));
}

i32 UpperBound(const vector<i32>& nums, const i32 key) {
    i32 lo = 0;
    i32 hi = nums.size() - 1;
    i32 ans = -1;
    while (lo <= hi) {
        const i32 mi = lo + (hi - lo) / 2;
        if (nums[mi] <= key) {
            lo = mi + 1;
        } else {
            ans = mi;
            hi = mi - 1;
        }
    }
    return ans;
}

i32 UpperBoundRec(const vector<i32>& nums, i32 key, i32 lo = -1, i32 hi = -1) {
    if (lo > hi) return INF;
    if (lo == -1) lo = 0;
    if (hi == -1) hi = size(nums) - 1;
    const i32 mi = lo + (hi - lo) / 2;
    if (nums[mi] <= key) return UpperBoundRec(nums, key, mi + 1, hi);
    return min(mi, UpperBoundRec(nums, key, lo, mi - 1));
}

i32 BinarySearch(const vector<i32>& nums, const i32 key) {
    i32 lo = 0;
    i32 hi = nums.size() - 1;
    while (lo <= hi) {
        const i32 mi = lo + (hi - lo) / 2;
        if (nums[mi] == key) {
            return mi;
        } else if (nums[mi] < key) {
            lo = mi + 1;
        } else {
            hi = mi - 1;
        }
    }
    return -1;
}

i32 BinarySearchRec(const vector<i32>& nums, i32 key, i32 lo, i32 hi) {
    if (lo > hi) return -1;
    const i32 mi = lo + (hi - lo) / 2;
    if (nums[mi] == key) return mi;
    if (nums[mi] < key) return BinarySearchRec(nums, key, mi + 1, hi);
    return BinarySearchRec(nums, key, lo, mi - 1);
}

i32 BinaryFirst(const vector<i32>& nums, const int key) {
    i32 lo = 0;
    i32 hi = nums.size() - 1;
    i32 ans = -1;
    while (lo <= hi) {
        const i32 mi = lo + (hi - lo) / 2;
        if (nums[mi] < key) {
            lo = mi + 1;
        } else if (nums[mi] == key) {
            ans = mi;
            hi = mi - 1;
        } else {
            hi = mi - 1;
        }
    }
    return ans;
}

i32 BinaryFirstRec(const vector<i32>& nums, i32 key, i32 lo, i32 hi) {
    if (lo > hi) return INF;
    const i32 mi = lo + (hi - lo) / 2;
    if (nums[mi] < key) return BinaryFirstRec(nums, key, mi + 1, hi);
    if (nums[mi] > key) return BinaryFirstRec(nums, key, lo, mi - 1);
    return min(mi, BinaryFirstRec(nums, key, lo, mi - 1));
}

i32 BinaryLast(const vector<i32>& nums, const int key) {
    i32 lo = 0;
    i32 hi = nums.size() - 1;
    i32 ans = -1;
    while (lo <= hi) {
        const i32 mi = lo + (hi - lo) / 2;
        if (nums[mi] < key) {
            lo = mi + 1;
        } else if (nums[mi] == key) {
            ans = mi;
            lo = mi + 1;
        } else {
            hi = mi - 1;
        }
    }
    return ans;
}

i32 BinaryLastRec(const vector<i32>& nums, i32 key, i32 lo, i32 hi) {
    if (lo > hi) return -1;
    const i32 mi = lo + (hi - lo) / 2;
    if (nums[mi] < key) return BinaryLastRec(nums, key, mi + 1, hi);
    if (nums[mi] > key) return BinaryLastRec(nums, key, lo, mi - 1);
    return max(mi, BinaryLastRec(nums, key, mi + 1, hi));
}

pair<i32, i32> Range(const vector<i32>& nums, const int key) {
    const int left = BinaryFirst(nums, key);
    const int right = BinaryLast(nums, key);
    return {left, right};
}

pair<i32, i32> RangeRec(const vector<i32>& nums, const int key) {
    const int left = BinaryFirstRec(nums, key, 0, size(nums) - 1);
    const int right = BinaryLastRec(nums, key, 0, size(nums) - 1);
    return {left, right};
}

i32 BinaryFirstLess(const vector<i32>& nums, const int key) {
    i32 lo = 0;
    i32 hi = nums.size() - 1;
    i32 ans = -1;
    while (lo <= hi) {
        const i32 mi = lo + (hi - lo) / 2;
        if (nums[mi] < key) {
            ans = mi;
            lo = mi + 1;
        } else if (nums[mi] == key) {
            hi = mi - 1;
        } else {
            hi = mi - 1;
        }
    }
    return ans;
}

i32 BinaryFirstGreater(const vector<i32>& nums, const int key) {
    i32 lo = 0;
    i32 hi = nums.size() - 1;
    i32 ans = -1;
    while (lo <= hi) {
        const i32 mi = lo + (hi - lo) / 2;
        if (nums[mi] < key) {
            lo = mi + 1;
        } else if (nums[mi] == key) {
            lo = mi + 1;
        } else {
            ans = mi;
            hi = mi - 1;
        }
    }
    return ans;
}

pair<i32, i32> RangeLtGt(const vector<i32>& nums, const int key) {
    const int left = BinaryFirstLess(nums, key);
    const int right = BinaryFirstGreater(nums, key);
    return {left, right};
}

int main() { // TimeMeasure _;
    assert(LowerBound({1,2,3,4,5,6,7,8,9}, 1) == 0);
    assert(LowerBound({1,2,3,4,5,6,7,8,9}, 0) == 0);
    assert(LowerBound({1,2,3,4,5,6,7,8,9}, 10) == -1);
    assert(LowerBound({1,2,3,4,5,6,7,8,9}, 4) == 3);
    assert(LowerBound({1,2,3,4,6,7,8,9}, 5) == 4);
    assert(LowerBound({1,2,3,3,3,3,3,4,6,7,8,9}, 3) == 2);
    assert(LowerBound({1,2,3,3,3,3,3,4,6,7,8,9}, 4) == 7);
    assert(LowerBound({1,3,3,3,3,3,4,6,7,8,9}, 2) == 1);

    assert(LowerBoundRec({1,2,3,4,5,6,7,8,9}, 1) == 0);
    assert(LowerBoundRec({1,2,3,4,5,6,7,8,9}, 0) == 0);
    assert(LowerBoundRec({1,2,3,4,5,6,7,8,9}, 10) == INF);
    assert(LowerBoundRec({1,2,3,4,5,6,7,8,9}, 4) == 3);
    assert(LowerBoundRec({1,2,3,4,6,7,8,9}, 5) == 4);
    assert(LowerBoundRec({1,2,3,3,3,3,3,4,6,7,8,9}, 3) == 2);
    assert(LowerBoundRec({1,2,3,3,3,3,3,4,6,7,8,9}, 4) == 7);
    assert(LowerBoundRec({1,3,3,3,3,3,4,6,7,8,9}, 2) == 1);

    assert(UpperBound({1,2,3,4,5,6,7,8,9}, 4) == 4);
    assert(UpperBound({1,2,3,4,5,6,7,8,9}, 8) == 8);
    assert(UpperBound({1,2,3,4,5,6,7,8,9}, 10) == -1);
    assert(UpperBound({1,2,3,4,5,6,7,8,9}, 0) == 0);
    assert(UpperBound({1,2,3,4,5,6,7,8,9}, 9) == -1);
    assert(UpperBound({1,2,3,3,3,3,3,4,6,7,8,9}, 3) == 7);

    assert(UpperBoundRec({1,2,3,4,5,6,7,8,9}, 4) == 4);
    assert(UpperBoundRec({1,2,3,4,5,6,7,8,9}, 8) == 8);
    assert(UpperBoundRec({1,2,3,4,5,6,7,8,9}, 10) == INF);
    assert(UpperBoundRec({1,2,3,4,5,6,7,8,9}, 0) == 0);
    assert(UpperBoundRec({1,2,3,4,5,6,7,8,9}, 9) == INF);
    assert(UpperBoundRec({1,2,3,3,3,3,3,4,6,7,8,9}, 3) == 7);

    assert(BinarySearch({1,2,3,4,5,6,7,8,9}, 4) == 3);
    assert(BinarySearch({1,2,3,4,5,6,7,8,9}, 10) == -1);

    assert(BinarySearchRec({1,2,3,4,5,6,7,8,9}, 4, 0, 8) == 3);
    assert(BinarySearchRec({1,2,3,4,5,6,7,8,9}, 10, 0, 8) == -1);

    assert((Range({1, 2, 8, 8, 8, 10, 10}, 8) == std::pair{2, 4}));
    assert((Range({1, 2, 8, 8, 10, 19, 19, 19}, 19) == std::pair{5, 7}));
    assert((Range({1, 1, 1, 2, 8, 8, 12, 19}, 1) == std::pair{0, 2}));

    assert((RangeRec({1, 2, 8, 8, 8, 10, 10}, 8) == std::pair{2, 4}));
    assert((RangeRec({1, 2, 8, 8, 10, 19, 19, 19}, 19) == std::pair{5, 7}));
    assert((RangeRec({1, 1, 1, 2, 8, 8, 12, 19}, 1) == std::pair{0, 2}));

    assert((RangeLtGt({1, 2, 8, 10, 10, 12, 19}, 0) == std::pair{-1, 0}));
    assert((RangeLtGt({1, 2, 8, 10, 10, 12, 19}, 5) == std::pair{1, 2}));
    assert((RangeLtGt({1, 2, 8, 10, 10, 12, 19}, 20) == std::pair{6, -1}));
    assert((RangeLtGt({1, 2, 8, 12, 19}, 10) == std::pair{2, 3}));
    assert((RangeLtGt({1, 2, 8, 10, 10, 12, 19}, 13) == std::pair{5, 6}));
}

// https://algorithmica.org/en/eytzinger