binary_search.cpp

#include <vector>

/**
 Given an non-decreasing ordered array `arr`, search the biggest `i` that makes `arr[i] == value`.
 If `i` doesn't exist, return -1
 */
int search_last_match(const std::vector<int>& arr, const int value)
{
    int lef = 0, rig = static_cast<int>(arr.size());
    while (rig-lef > 1)
    {
        const int mid = (lef+rig)/2;
        if (arr[mid] <= value)
            lef = mid;
        else
            rig = mid;
    }
    return arr[lef] == value ? lef : -1;
}

/**
 Given an non-decreasing ordered array `arr`, search the smallest `i` that makes `arr[i] == value`.
 If `i` doesn't exist, return -1
 */
int search_first_match(const std::vector<int>& arr, const int value)
{
    int lef = -1, rig = static_cast<int>(arr.size())-1;
    while (rig-lef > 1)
    {
        const int mid = (lef+rig)/2;
        if (arr[mid] >= value)
            rig = mid;
        else
            lef = mid;
    }
    return arr[rig] == value ? rig : -1;
}

/**
 Given an non-decreasing ordered array `arr`, search the biggest `i` that makes `arr[i] < value`.
 If `i` doesn't exist, return -1
 */
int search_last_less(const std::vector<int>& arr, const int value)
{
    if (arr.front() >= value)
        return -1;
    
    int lef = 0, rig = static_cast<int>(arr.size());
    while (rig-lef > 1)
    {
        const int mid = (lef+rig)/2;
        if (arr[mid] < value)
            lef = mid;
        else
            rig = mid;
    }
    return lef;
}

/**
 Given an non-decreasing ordered array `arr`, search the smallest `i` that makes `arr[i] > value`.
 If `i` doesn't exist, return -1
 */
int search_first_greater(const std::vector<int>& arr, const int value)
{
    if (arr.back() <= value)
        return -1;
    
    int lef = -1, rig = static_cast<int>(arr.size())-1;
    while (rig-lef > 1)
    {
        const int mid = (lef+rig)/2;
        if (arr[mid] > value)
            rig = mid;
        else
            lef = mid;
    }
    return rig;
}