Repository: SerenityOS/serenity
File: AK/BinarySearch.h (C/C++)

Code before:
        else {
            if (nearby_index)
                *nearby_index = middle;
            return &haystack[middle];
        }
    }

    if (nearby_index)
        *nearby_index = min(low, high);

    return nullptr;
}

// Unlike their std equivalents, these two function require the entire Container to be sorted!
// std::[lower,upper]_bound only require the array to be sorted after and before, respectively, the needle.

template<typename Container, typename Needle, typename Comparator = DefaultComparator, typename Return = decltype(&Container {}[0])>
constexpr auto lower_bound(
    Container&& haystack,
    Needle&& needle,
    Comparator comparator = Comparator {}) -> size_t
{
    size_t index {};
    binary_search(haystack, needle, &index, comparator);
    if (index > 0 && haystack[index] >= needle)
        index -= 1;
    return index;
}

template<typename Container, typename Needle, typename Comparator = DefaultComparator, typename Return = decltype(&Container {}[0])>
constexpr auto upper_bound(
    Container&& haystack,
    Needle&& needle,
    Comparator comparator = Comparator {}) -> size_t
{
    size_t index {};
    binary_search(haystack, needle, &index, comparator);
    if (index < haystack.size() - 1 && haystack[index] <= needle)
        index += 1;
    return index;
}

}

#if USING_AK_GLOBALLY
using AK::binary_search;
using AK::lower_bound;
using AK::upper_bound;
#endif


Review comment (bug):
won't this do the wrong this for e.g. `lower_bound({1, 2, 2, 2, 2, 2, 2, 3}, 2)`? binary_search will return a 2 in the middle, and then you only go one left at most, when you need to go quite a bit to the left.

Code after:
        *nearby_index = high;
    if (comparator(needle, haystack[high]) == 0)
        return &haystack[high];
    return nullptr;
}

// Unlike their std equivalents, these two function require the entire Container to be sorted!
// std::[lower,upper]_bound only require the array to be sorted after and before, respectively, the needle.

template<typename Container, typename Needle, typename Comparator = DefaultComparator, typename Return = decltype(&Container {}[0])>
constexpr auto lower_bound(
    Container&& haystack,
    Needle&& needle,
    Comparator comparator = {}) -> Optional<size_t>
{
    size_t index {};
    binary_search(haystack, needle, &index, comparator);
    if (index == haystack.size() - 1 && comparator(needle, haystack[index]) > 0)
        return OptionalNone {};
    return index;
}

template<typename Container, typename Needle, typename Comparator = DefaultComparator, typename Return = decltype(&Container {}[0])>
constexpr auto strict_lower_bound(
    Container&& haystack,
    Needle&& needle,
    Comparator comparator = {}) -> Optional<size_t>
{
    // lower_bound give you the "first element x such that i ≤ x".
    // This gives you the last element x such that x < i.
    size_t index {};
    binary_search(haystack, needle, &index, comparator);
    if (index > 0 && comparator(needle, haystack[index]) <= 0)
        index--;

    if (index == 0 && comparator(needle, haystack[index]) <= 0)
        return OptionalNone {};
    return index;
}

struct UpperBoundComparator {
    template<typename T, typename S>
    [[nodiscard]] constexpr int operator()(T& lhs, S& rhs)
    {
        if (lhs >= rhs)
            return 1;
        return -1;
    }
};

template<typename Container, typename Needle, typename Comparator = UpperBoundComparator, typename Return = decltype(&Container {}[0])>