binary_search.h

#ifndef BINARY_SEARCH_H
#define BINARY_SEARCH_H
 
#ifdef __cplusplus
#include <cstdint>
#include <iostream>
#include <vector>
#endif

template <typename T> int64_t bin_search(std::vector<T> arr, int64_t left, int64_t right, T x) {
    while (left <= right) {
        int64_t mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            return mid;
        }
        if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // element not found
}

template <typename T> int64_t lower_bound(std::vector<T> arr, int64_t left, int64_t right, T x) {
    int64_t result = right, mid = 0;
    --right;
 
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (arr[mid] >= x) {
            result = mid;
            // look for smaller index on the left
            right = mid - 1;
        } else {
            left = mid + 1; // look on the right
        }
    }
    return result;
}

template <typename T> int64_t upper_bound(std::vector<T> arr, int64_t left, int64_t right, T x) {
    int64_t result = right, mid = 0;
    --right;
 
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (arr[mid] > x) {
            result = mid;
            // look for smaller index on the left
            right = mid - 1;
        } else {
            left = mid + 1; // look on the right
        }
    }
    return result;
}
 
#endif