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

Code before:
        *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);
    return index;
}

// FIXME: Relax the constraint on the type.
//        Given the array {1, 2, 4, 5, 5, 6} and searching for 5 we want upper_bound
//        to return 5. The binary search for 5 will return the first matching element
//        so we will get the index 3. The workaround that I used here to be able to
//        leverage the binary search is to look for the very next element: 6 (++needle).
//        This however means that the input type needs to properly define a "next one",
//        which I expressed as being an integer.
template<typename Container, typename Needle, typename Comparator = DefaultComparator, typename Return = decltype(&Container {}[0])>
requires IsIntegral<RemoveReference<Needle>>
constexpr auto upper_bound(
    Container&& haystack,
    Needle&& needle,
    Comparator comparator = Comparator {}) -> size_t
{
    size_t index {};
    binary_search(haystack, needle + 1, &index, comparator);
    return index;
}

}

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


Review comment (suggestion):
Shouldn't


```
  size_t index = 0;
  binary_search(haystack, needle, &index, [](T& lhs, S& rhs) ( return comparator(rhs, lhs); });
  return index;
```

do the trick? (i.e. swap lhs and rhs to invert the comparator)

Code after:
{
    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])>
requires IsIntegral<RemoveReference<Needle>>
constexpr auto upper_bound(
    Container&& haystack,
    Needle&& needle,
    Comparator comparator = {}) -> Optional<size_t>
{
    size_t index = 0;
    binary_search(haystack, needle, &index, comparator);
    if (index == haystack.size() - 1 && comparator(needle, haystack[index]) >= 0)
        return OptionalNone {};
    return index;
}

}