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

Code before:
        return 0;
    }
};

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

    size_t low = 0;
    size_t high = haystack.size() - 1;
    while (low <= high) {
        size_t middle = low + (high - low) / 2;

        int comparison = comparator(needle, haystack[middle]);

        if (comparison <= 0)
            if (middle != 0 && high != middle)
                high = middle;
            else {
                if (comparison == 0) {
                    if (nearby_index)
                        *nearby_index = middle;
                    return &haystack[middle];
                }
                break;
            }
        else if (comparison > 0)
            low = middle + 1;
        else {
            if (nearby_index)
                *nearby_index = middle;
            return &haystack[middle];
        }
    }

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

    return nullptr;
}

}

Review comment (bug):
I know it's on the LHS too, but the `!= 0` feels a bit off. Is the intent `!= low`?

I have to admit, I always find binary searches hard to think about if there isn't a clear invariant and if the loop body isn't very simple. Since we want to find the leftmost instance of `needle`, `haystack[high]` should always be `>= needle`, and that should be invariant, right?

So, would this work?

```
    size_t low = 0;
    size_t high = haystack.size() - 1;
    while (low != high) {
        size_t middle = low + (high - low) / 2;
        int comparison = comparator(needle, haystack[middle]);
        if (comparison <= 0)
            high = middle;
        else
            low = middle + 1;
    }

    if (nearby_index)
        *nearby_index = high;
    if (comparator(needle, haystack[high]) == 0)
        return &haystack[high];
    return nullptr;
```

Code after:

        return 0;
    }
};

template<typename Container, typename Needle, typename Comparator = DefaultComparator>
constexpr auto binary_search(
    Container&& haystack,
    Needle&& needle,
    size_t* nearby_index = nullptr,
    Comparator comparator = Comparator {}) -> decltype(&haystack[0])
{
    if (haystack.size() == 0) {
        // FIXME: Refactor the function's API to make it always return a valid index.
        if (nearby_index)
            *nearby_index = 0;
        return nullptr;
    }

    size_t low = 0;
    size_t high = haystack.size() - 1;
    while (low != high) {
        size_t middle = low + (high - low) / 2;
        int comparison = comparator(needle, haystack[middle]);
        if (comparison <= 0)
            high = middle;
        else
            low = middle + 1;
    }

    if (nearby_index)
        *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;