[libc++][ranges] Implement ranges::binary_search and ranges::{lower, upper}_bound

[var-const]

libcxx/docs/Status/RangesAlgorithms.csv

14–15

Can you please add a link to this patch?

libcxx/include/__algorithm/ranges_lower_bound.h

37

I think for consistency with other patches, it should use longer names (_Iterator, etc.).

42

Nit: can you split this function into ~3 logical blocks? I find it a little hard(er) to read as a monolithic block of code. I'd suggest a blank line before while (to separate the initial setup from the main part), before the return statement (similarly to make the main part stand out), and either before or after the call to std::advance.

libcxx/include/__algorithm/ranges_upper_bound.h

39

Nit: similar to another patch, can you name this lambda something like __comp_lhs_rhs_swapped? (or just __comp_swapped)

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp

3

(please note that many comments in this file apply to other test files as well)

72

Similar to another patch, it probably makes sense to test that the comparator works when:

• it takes the arguments by non-const lvalue;
• its operator() is not const;
• it returns something convertible to bool.

133

I'd add tests for:

• 1 element range (too small to meaningfully divide in half);
• even number of elements;
• odd number of elements;
• the searched-for element is the first one;
• the searched-for element is the last one;
• all elements other than the searched-for element are equal.

178

Please add return 0.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges.upper_bound.pass.cpp

66

Optional: perhaps check the return type here as well?

[var-const]

libcxx/include/__algorithm/ranges_lower_bound.h

39

Have you considered sharing the implementation of the algorithm between the ranges and non-ranges versions? This algorithm, while not very complicated, isn't trivial and is quite prone to off-by-one errors. Personally, I'm on the fence.

(cc'ing @ldionne as well)

[philnik]

• Address comments

[philnik]

libcxx/include/__algorithm/ranges_lower_bound.h

39

Yes, but I think it's simple enough to not warrant sharing the implementation, but I'm on the fence too.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp

72

I'll add the convertible to bool tests once D122011 landed. Taking only non-const lvalues doesn't model indirect_strict_weak_order.

[philnik]

• Rebased
• Fix linters

[Mordante]

In general looks good, but some remarks.

libcxx/include/CMakeLists.txt

78

Were these files not already in CMakeLists.txt?

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp

62

assert(base(ret)); looks wrong, I expect this should be assert(ret);

163

Please add some tests for the complexity requirements for comparisons and projections.
The same for lower_bound and upper_bound.

[philnik]

libcxx/include/CMakeLists.txt

78

I guess you mean the find things? Must have been a merge conflict.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp

163

How exactly would you like them to look like? The standard says that the complexity is log_2(last - first) + O(1) How could I (without a statistical analysis) find out what the constant is?

[philnik]

• Address comments

[var-const]

LGTM. Please check with @ldionne regarding whether it's best to share the implementation of the algorithm with the non-ranges version.

[Mordante]

LGTM! But please address @var-const's request before landing.

libcxx/include/__algorithm/ranges_lower_bound.h

39

I don't have a strong opinion whether to combine these two versions or keep them separate. std::invoke requires C++17, but our implementation of std::invoke uses std::__invoke requires C++11. So it seems to be an issue to use invoke on C++03.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp

163

Good point O(1) makes it hard :-( std::search's O(1) can differ from std::lower_bound's O(1).

[philnik]

• Try to fix GCC

[ldionne]

Sorry for being MIA, but I do have a few comments. Some of them may apply to algorithms that we've shipped previously as well.

libcxx/include/__algorithm/ranges_lower_bound.h

39

I would really like to share this with the implementation in <__algorithm/__lower_bound.h>. I suspect it's not too difficult to do that, and we'll avoid duplicating code.

41

Shouldn't this be ranges::distance?

libcxx/include/__algorithm/ranges_upper_bound.h

50

Should we be forwarding __lhs and __rhs? I think we're not losing anything if we do it, and I suspect we might be required to (if so, then we're also missing a test case).

51

This is not ADL-proof. Same above. I think we should have ADL proofing tests for ranges algorithms.

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_upper_bound.h

50

indirect_strict_weak_order requires that _Comp is equality preserving (meaning that cv ref qualifications still give the same output) and it's callable with l- and rvalues, so only the const-ness has to stay (unless I missed some requirement). Because of this I see no reason to make the code harder to read. I think this should actually just be auto& __lhs, auto& __rhs.

51

The design of projected isn't ADL-proof, so we can't add tests. If you want more context see https://wg21.link/P2538.

[philnik]

libcxx/include/__algorithm/ranges_upper_bound.h

50

Ignore the last part. Using auto& would just make the implementation weirder.

[philnik]

• Try to fix CI

[philnik]

• Try to fix CI

[philnik]

• Next try

[philnik]

• Rebased
• Add benchmark

[ldionne]

LGTM with my comments addressed. I don't think I need to see this again whatever you do for the auto const& issue.

libcxx/include/__algorithm/equal_range.h

54 ↗

(On Diff #433724)

Can you please make sure that we have a test for the STL classic algorithms that will fail if you make a copy of __comp here? You can just add auto __dummy = __comp; (void)__dummy; to test it.

libcxx/include/__algorithm/lower_bound.h

47–48 ↗

(On Diff #433724)

Can you please add a libc++ specific test to check that we diagnose if you pass something that isn't a proper function object to lower_bound (and the other algorithms in this patch too), please?

libcxx/include/__algorithm/ranges_upper_bound.h

50

If it's true that cv-qualification doesn't matter, perhaps we should make this auto const& instead? That definitely removes a mental burden when reading this sort of code, IMO.

[philnik]

• Address comments

libcxx/include/__algorithm/equal_range.h

54 ↗

(On Diff #433724)

We've got libcxx/algorithms/robust_against_copying_comparators.pass.cpp.

[philnik]

• Try to fix CI

[EricWF]

Amazing tests. Unfortunately, this change causes breakages in std::lower_bound because ranges::distance is not a drop-in replacement for std::distance, and that breaks existing code as it switches between C++17 and C++20.
I'm working on minimizing a reproducer.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp

9

Great tests BTW.

libcxx/docs/Status/RangesAlgorithms.csv

 Category,Algorithm,Assignee,CL,Complete
 Search,any_of,Christopher Di Bella,`D105793 <https://llvm.org/D105793>`_
 Search,all_of,Christopher Di Bella,`D105793 <https://llvm.org/D105793>`_
 Search,none_of,Christopher Di Bella,`D105793 <https://llvm.org/D105793>`_
 Search,find,Nikolas Klauser,`D121248 <https://reviews.llvm.org/D121248>`_,✅
 Search,find_if,Nikolas Klauser,`D121248 <https://reviews.llvm.org/D121248>`_,✅
 Search,find_if_not,Nikolas Klauser,`D121248 <https://reviews.llvm.org/D121248>`_,✅
 Search,find_first_of,Not assigned,n/a,Not started
 Search,adjacent_find,Not assigned,n/a,Not started
 Search,mismatch,Nikolas Klauser,`D117817 <https://llvm.org/D117817>`_,✅
 Search,equal,Not assigned,n/a,Not started
 Search,lexicographical_compare,Not assigned,n/a,Not started
 Search,partition_point,Christopher Di Bella,`D105794 <https://llvm.org/D105794>`_,Under review
-Search,lower_bound,Christopher Di Bella,`D105795 <https://llvm.org/D105795>`_,Under review
-Search,upper_bound,Christopher Di Bella,`D105795 <https://llvm.org/D105795>`_,Under review
+Search,lower_bound,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
+Search,upper_bound,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,equal_range,Christopher Di Bella,n/a,Not started
-Search,binary_search,Christopher Di Bella,n/a,Not started
+Search,binary_search,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,min,Nikolas Klauser,`D119589 <https://llvm.org/D119589>`_,✅
 Search,max,Nikolas Klauser,`D122002 <https://llvm.org/D122002>`_,✅
 Search,minmax,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅
 Search,min_element,Nikolas Klauser,`D117025 <https://llvm.org/D117025>`_,✅
 Search,max_element,Nikolas Klauser,`D117523 <https://llvm.org/D117523>`_,✅
 Search,minmax_element,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅
 Search,count,Nikolas Klauser, `D121523 <https://llvm.org/D121523>`_,✅
 Search,count_if,Nikolas Klauser, `D121523 <https://llvm.org/D121523>`_,✅

libcxx/include/CMakeLists.txt

set(files
   __algorithm/partial_sort.h
   __algorithm/partial_sort_copy.h
   __algorithm/partition.h
   __algorithm/partition_copy.h
   __algorithm/partition_point.h
   __algorithm/pop_heap.h
   __algorithm/prev_permutation.h
   __algorithm/push_heap.h
+  __algorithm/ranges_binary_search.h
   __algorithm/ranges_count.h
   __algorithm/ranges_count_if.h
   __algorithm/ranges_find.h
   __algorithm/ranges_find_if.h
   __algorithm/ranges_find_if_not.h
+  __algorithm/ranges_lower_bound.h
   __algorithm/ranges_max.h
+  __algorithm/ranges_binary_search.h
+  __algorithm/ranges_find.h
+  __algorithm/ranges_find_if.h
+  __algorithm/ranges_find_if_not.h
+  __algorithm/ranges_lower_bound.h
   __algorithm/ranges_max_element.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.h
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
+  __algorithm/ranges_upper_bound.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h
   __algorithm/remove_if.h
   __algorithm/replace.h
   __algorithm/replace_copy.h
   __algorithm/replace_copy_if.h
   __algorithm/replace_if.h

libcxx/include/__algorithm/ranges_binary_search.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_BINARY_SEARCH_H
+#define _LIBCPP___ALGORITHM_RANGES_BINARY_SEARCH_H
+
+#include <__algorithm/ranges_lower_bound.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __binary_search {
+struct __fn {
+  template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity,
+            indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  bool operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+    auto __ret = ranges::__lower_bound_impl(__first, __last, __value, __comp, __proj);
+    return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first));
+  }
+
+  template <forward_range _Range, class _Type, class _Proj = identity,
+            indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  bool operator()(_Range&& __r, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+    auto __first = ranges::begin(__r);
+    auto __last = ranges::end(__r);
+    auto __ret = ranges::__lower_bound_impl(__first, __last, __value, __comp, __proj);
+    return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first));
+  }
+};
+} // namespace __binary_search
+
+inline namespace __cpo {
+  inline constexpr auto binary_search = __binary_search::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_BINARY_SEARCH_H

libcxx/include/__algorithm/ranges_lower_bound.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_LOWER_BOUND_H
+#define _LIBCPP___ALGORITHM_RANGES_LOWER_BOUND_H
+
+#include <__algorithm/half_positive.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/advance.h>
+#include <__iterator/concepts.h>
+#include <__iterator/distance.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
+template <class _Iter, class _Sent, class _Type, class _Proj, class _Comp>
+_LIBCPP_HIDE_FROM_ABI constexpr
+_Iter __lower_bound_impl(_Iter __first, _Sent __last, const _Type& __value, _Comp& __comp, _Proj& __proj) {
+  using __diff_t = typename iterator_traits<_Iter>::difference_type;
+  __diff_t __len = std::distance(__first, __last);
+
+  while (__len != 0) {
+    __diff_t __len2 = std::__half_positive(__len);
+    _Iter __m = __first;
+    std::advance(__m, __len2);
+    if (std::invoke(__comp, std::invoke(__proj, *__m), __value)) {
+      __first = ++__m;
+      __len -= __len2 + 1;
+    } else {
+      __len = __len2;
+    }
+  }
+
+  return __first;
+}
+
+namespace __lower_bound {
+struct __fn {
+  template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity,
+            indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Iter operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+    return ranges::__lower_bound_impl(__first, __last, __value, __comp, __proj);
+  }
+
+  template <forward_range _Range, class _Type, class _Proj = identity,
+            indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Range> operator()(_Range&& __r,
+                                         const _Type& __value,
+                                         _Comp __comp = {},
+                                         _Proj __proj = {}) const {
+    return ranges::__lower_bound_impl(ranges::begin(__r), ranges::end(__r), __value, __comp, __proj);
+  }
+};
+} // namespace __lower_bound
+
+inline namespace __cpo {
+  inline constexpr auto lower_bound = __lower_bound::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_LOWER_BOUND_H

libcxx/include/__algorithm/ranges_upper_bound.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_UPPER_BOUND_H
+#define _LIBCPP___ALGORITHM_RANGES_UPPER_BOUND_H
+
+#include <__algorithm/ranges_lower_bound.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __upper_bound {
+struct __fn {
+  template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity,
+            indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Iter operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+    auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return !std::invoke(__comp, __rhs, __lhs); };
+    return __lower_bound_impl(__first, __last, __value, __comp_lhs_rhs_swapped, __proj);
+  }
+
+  template <forward_range _Range, class _Type, class _Proj = identity,
+            indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Range> operator()(_Range&& __r,
+                                         const _Type& __value,
+                                         _Comp __comp = {},
+                                         _Proj __proj = {}) const {
+    auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return !std::invoke(__comp, __rhs, __lhs); };
+    return __lower_bound_impl(ranges::begin(__r), ranges::end(__r), __value, __comp_lhs_rhs_swapped, __proj);
+  }
+};
+} // namespace __upper_bound
+
+inline namespace __cpo {
+  inline constexpr auto upper_bound = __upper_bound::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_UPPER_BOUND_H

libcxx/include/algorithm

template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
            indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
     constexpr ranges::minmax_element_result<I>
       minmax_element(I first, S last, Comp comp = {}, Proj proj = {});                    // since C++20
 
   template<forward_range R, class Proj = identity,
            indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
     constexpr ranges::minmax_element_result<borrowed_iterator_t<R>>
       minmax_element(R&& r, Comp comp = {}, Proj proj = {});                              // since C++20
+
+  template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+           indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+    constexpr I upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
+
+  template<forward_range R, class T, class Proj = identity,
+           indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+             ranges::less>
+    constexpr borrowed_iterator_t<R>
+      upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});                     // since C++20
+
+  template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+           indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+    constexpr I lower_bound(I first, S last, const T& value, Comp comp = {},
+                                    Proj proj = {});                                          // since C++20
+  template<forward_range R, class T, class Proj = identity,
+           indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+             ranges::less>
+    constexpr borrowed_iterator_t<R>
+      lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});                     // since C++20
+
+  template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+           indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+    constexpr bool binary_search(I first, S last, const T& value, Comp comp = {},
+                                         Proj proj = {});                                     // since C++20
+  template<forward_range R, class T, class Proj = identity,
+           indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+             ranges::less>
+    constexpr bool binary_search(R&& r, const T& value, Comp comp = {},
+                                         Proj proj = {});                                     // since C++20
+
 }
 
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/partial_sort.h>
 #include <__algorithm/partial_sort_copy.h>
 #include <__algorithm/partition.h>
 #include <__algorithm/partition_copy.h>
 #include <__algorithm/partition_point.h>
 #include <__algorithm/pop_heap.h>
 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/push_heap.h>
+#include <__algorithm/ranges_binary_search.h>
 #include <__algorithm/ranges_count.h>
 #include <__algorithm/ranges_count_if.h>
 #include <__algorithm/ranges_find.h>
 #include <__algorithm/ranges_find_if.h>
 #include <__algorithm/ranges_find_if_not.h>
+#include <__algorithm/ranges_lower_bound.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
+#include <__algorithm/ranges_upper_bound.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>
 #include <__algorithm/remove_if.h>
 #include <__algorithm/replace.h>
 #include <__algorithm/replace_copy.h>
 #include <__algorithm/replace_copy_if.h>
 #include <__algorithm/replace_if.h>

libcxx/include/module.modulemap

module __algorithm {
       module partition                { private header "__algorithm/partition.h" }
       module partition_copy           { private header "__algorithm/partition_copy.h" }
       module partition_point          { private header "__algorithm/partition_point.h" }
       module pop_heap                 { private header "__algorithm/pop_heap.h" }
       module prev_permutation         { private header "__algorithm/prev_permutation.h" }
       module push_heap                { private header "__algorithm/push_heap.h" }
       module ranges_count             { private header "__algorithm/ranges_count.h" }
       module ranges_count_if          { private header "__algorithm/ranges_count_if.h" }
+      module ranges_binary_search     { private header "__algorithm/ranges_binary_search.h" }
       module ranges_find              { private header "__algorithm/ranges_find.h" }
       module ranges_find_if           { private header "__algorithm/ranges_find_if.h" }
       module ranges_find_if_not       { private header "__algorithm/ranges_find_if_not.h" }
+      module ranges_lower_bound       { private header "__algorithm/ranges_lower_bound.h" }
       module ranges_max               { private header "__algorithm/ranges_max.h" }
       module ranges_max_element       { private header "__algorithm/ranges_max_element.h" }
       module ranges_min               { private header "__algorithm/ranges_min.h" }
       module ranges_min_element       { private header "__algorithm/ranges_min_element.h" }
       module ranges_minmax            { private header "__algorithm/ranges_minmax.h" }
       module ranges_minmax_element    { private header "__algorithm/ranges_minmax_element.h" }
       module ranges_mismatch          { private header "__algorithm/ranges_mismatch.h" }
       module ranges_swap_ranges       { private header "__algorithm/ranges_swap_ranges.h" }
       module ranges_transform         { private header "__algorithm/ranges_transform.h" }
+      module ranges_upper_bound       { private header "__algorithm/ranges_upper_bound.h" }
       module remove                   { private header "__algorithm/remove.h" }
       module remove_copy              { private header "__algorithm/remove_copy.h" }
       module remove_copy_if           { private header "__algorithm/remove_copy_if.h" }
       module remove_if                { private header "__algorithm/remove_if.h" }
       module replace                  { private header "__algorithm/replace.h" }
       module replace_copy             { private header "__algorithm/replace_copy.h" }
       module replace_copy_if          { private header "__algorithm/replace_copy_if.h" }
       module replace_if               { private header "__algorithm/replace_if.h" }

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

constexpr bool all_the_algorithms()
 
     int copies = 0;
     //(void)std::ranges::adjacent_find(first, last, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::adjacent_find(a, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::all_of(first, last, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::all_of(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::any_of(first, last, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::any_of(a, UnaryTrue(&copies)); assert(copies == 0);
-    //(void)std::ranges::binary_search(first, last, value, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::binary_search(a, value, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::binary_search(first, last, value, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::binary_search(a, value, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::clamp(value, value, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0);
 #if TEST_STD_VER > 20
     //(void)std::ranges::ends_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
 #endif
#endif
     //(void)std::ranges::is_sorted(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::is_sorted(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::is_sorted_until(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::is_sorted_until(a, Less(&copies)); assert(copies == 0);
     //if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(first, mid, last, Less(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(a, mid, Less(&copies)); assert(copies == 0); }
     //(void)std::ranges::lexicographical_compare(first, last, first2, last2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::lexicographical_compare(a, b, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::lower_bound(first, last, value, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::lower_bound(a, value, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::lower_bound(first, last, value, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::lower_bound(a, value, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::make_heap(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::make_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::max(value, value, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::max({ value, value }, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::max(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max_element(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max_element(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::merge(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
#endif
     //(void)std::ranges::transform(first, last, first2, UnaryTransform(&copies)); assert(copies == 0);
     //(void)std::ranges::transform(a, first2, UnaryTransform(&copies)); assert(copies == 0);
     //(void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(&copies)); assert(copies == 0);
     //(void)std::ranges::transform(a, b, first2, BinaryTransform(&copies)); assert(copies == 0);
     //(void)std::ranges::unique(first, last, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::unique(a, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::unique_copy(first, last, first2, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::unique_copy(a, first2, Equal(&copies)); assert(copies == 0);
-    //(void)std::ranges::upper_bound(first, last, value, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::upper_bound(a, value, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::upper_bound(first, last, value, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::upper_bound(a, value, Less(&copies)); assert(copies == 0);
 
     return true;
 }
 
 int main(int, char**)
 {
     all_the_algorithms();
     static_assert(all_the_algorithms());
 
     return 0;
 }

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/partial_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partial_sort.h'}}
 #include <__algorithm/partial_sort_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partial_sort_copy.h'}}
 #include <__algorithm/partition.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partition.h'}}
 #include <__algorithm/partition_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partition_copy.h'}}
 #include <__algorithm/partition_point.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partition_point.h'}}
 #include <__algorithm/pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pop_heap.h'}}
 #include <__algorithm/prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/prev_permutation.h'}}
 #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}}
+#include <__algorithm/ranges_binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_binary_search.h'}}
 #include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}}
 #include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}}
 #include <__algorithm/ranges_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find.h'}}
 #include <__algorithm/ranges_find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if.h'}}
 #include <__algorithm/ranges_find_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}}
+#include <__algorithm/ranges_lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lower_bound.h'}}
 #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}}
 #include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
 #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}}
 #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}}
 #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}}
 #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}}
 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
 #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
 #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
+#include <__algorithm/ranges_upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}
 #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.h'}}
 #include <__algorithm/remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy.h'}}
 #include <__algorithm/remove_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy_if.h'}}
 #include <__algorithm/remove_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_if.h'}}
 #include <__algorithm/replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/replace.h'}}
 #include <__algorithm/replace_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/replace_copy.h'}}
 #include <__algorithm/replace_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/replace_copy_if.h'}}
 #include <__algorithm/replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/replace_if.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+//          indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+//   constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {},
+//                                        Proj proj = {});
+// template<forward_range R, class T, class Proj = identity,
+//          indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+//            ranges::less>
+//   constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {},
+//                                        Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+struct NotLessThanComparable {};
+
+template <class It, class Sent = It>
+concept HasLowerBoundIt = requires(It it, Sent sent) { std::ranges::binary_search(it, sent, 1); };
+
+static_assert(HasLowerBoundIt<int*>);
+static_assert(!HasLowerBoundIt<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>);
+static_assert(!HasLowerBoundIt<ForwardIteratorNotDerivedFrom>);
+static_assert(!HasLowerBoundIt<ForwardIteratorNotIncrementable>);
+static_assert(!HasLowerBoundIt<NotLessThanComparable*>);
+
+template <class Range>
+concept HasLowerBoundR = requires(Range range) { std::ranges::binary_search(range, 1); };
+
+static_assert(HasLowerBoundR<std::array<int, 1>>);
+static_assert(!HasLowerBoundR<ForwardRangeNotDerivedFrom>);
+static_assert(!HasLowerBoundR<ForwardRangeNotIncrementable>);
+static_assert(!HasLowerBoundR<UncheckedRange<NotLessThanComparable*>>);
+
+template <class Pred>
+concept HasLowerBoundPred = requires(int* it, Pred pred) {std::ranges::binary_search(it, it, 1, pred); };
+
+static_assert(HasLowerBoundPred<std::ranges::less>);
+static_assert(!HasLowerBoundPred<IndirectUnaryPredicateNotCopyConstructible>);
+static_assert(!HasLowerBoundPred<IndirectUnaryPredicateNotPredicate>);
+
+template <class It>
+constexpr void test_iterators() {
+  { // simple test
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      std::same_as<bool> auto ret = std::ranges::binary_search(It(a), It(a + 6), 3);
+      assert(base(ret));
+    }
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      std::same_as<bool> auto ret = std::ranges::binary_search(range, 3);
+      assert(base(ret));
+    }
+  }
+
+  { // check that the predicate is used
+    int a[] = {6, 5, 4, 3, 2, 1};
+    assert(std::ranges::binary_search(It(a), It(a + 6), 2, std::ranges::greater{}));
+    auto range = std::ranges::subrange(It(a), It(a + 6));
+    assert(std::ranges::binary_search(range, 2, std::ranges::greater{}));
+  }
+
+  { // check that the projection is used
+    int a[] = {1, 2, 3, 4, 5, 6};
+    assert(std::ranges::binary_search(It(a), It(a + 6), 0, {}, [](int i) { return i - 3; }));
+    auto range = std::ranges::subrange(It(a), It(a + 6));
+    assert(std::ranges::binary_search(range, 0, {}, [](int i) { return i - 3; }));
+  }
+
+  { // check that true is returned with multiple matches
+    int a[] = {1, 2, 2, 2, 3};
+    assert(std::ranges::binary_search(It(a), It(a + 5), 2));
+    auto range = std::ranges::subrange(It(a), It(a + 5));
+    assert(std::ranges::binary_search(range, 2));
+  }
+
+  { // check that false is returned if all elements compare less than
+    int a[] = {1, 2, 3, 4};
+    assert(!std::ranges::binary_search(It(a), It(a + 4), 5));
+    auto range = std::ranges::subrange(It(a), It(a + 4));
+    assert(!std::ranges::binary_search(a, 5));
+  }
+
+  { // check that false is returned if no element compares less than
+    int a[] = {1, 2, 3, 4};
+    assert(!std::ranges::binary_search(It(a), It(a + 4), 0));
+    auto range = std::ranges::subrange(It(a), It(a + 4));
+    assert(!std::ranges::binary_search(range, 0));
+  }
+
+  { // check that a single element works
+    int a[] = {1};
+    assert(std::ranges::binary_search(It(a), It(a + 1), 1));
+    auto range = std::ranges::subrange(It(a), It(a + 1));
+    assert(std::ranges::binary_search(range, 1));
+  }
+
+  { // check that an even number of elements works and that searching for the first element works
+    int a[] = {1, 2, 7, 8, 10, 11};
+    assert(std::ranges::binary_search(It(a), It(a + 6), 1));
+    auto range = std::ranges::subrange(It(a), It(a + 6));
+    assert(std::ranges::binary_search(range, 1));
+  }
+
+  { // check that an odd number of elements works and that searching for the last element works
+    int a[] = {1, 2, 7, 10, 11};
+    assert(std::ranges::binary_search(It(a), It(a + 5), 11));
+    auto range = std::ranges::subrange(It(a), It(a + 5));
+    assert(std::ranges::binary_search(range, 11));
+  }
+
+  { // check that it works when all but the searched for elements are equal
+    int a[] = {1, 2, 2, 2, 2};
+    assert(std::ranges::binary_search(It(a), It(a + 5), 1));
+    auto range = std::ranges::subrange(It(a), It(a + 5));
+    assert(std::ranges::binary_search(range, 1));
+  }
+}
+
+constexpr bool test() {
+  test_iterators<int*>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+
+  { // check that std::invoke is used
+    struct S { int check; int other; };
+    S a[] = {{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}};
+    assert(std::ranges::binary_search(a, a + 6, 4, {}, &S::check));
+    assert(std::ranges::binary_search(a, 4, {}, &S::check));
+  }
+
+  { // check that an empty range works
+    std::array<int, 0> a;
+    assert(!std::ranges::binary_search(a.begin(), a.end(), 1));
+    assert(!std::ranges::binary_search(a, 1));
+  }
+
+  { // check that a non-const operator() works
+    struct Func {
+      constexpr bool operator()(const int& i, const int& j) { return i < j; }
+    };
+    int a[] = {1, 6, 9, 10, 23};
+    assert(std::ranges::binary_search(a, 6, Func{}));
+    assert(std::ranges::binary_search(a, a + 5, 6, Func{}));
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges.lower_bound.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+//          indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+//   constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {},
+//                                   Proj proj = {});
+// template<forward_range R, class T, class Proj = identity,
+//          indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+//            ranges::less>
+//   constexpr borrowed_iterator_t<R>
+//     ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+struct NotLessThanComparable {};
+
+template <class It, class Sent = It>
+concept HasLowerBoundIt = requires(It it, Sent sent) { std::ranges::lower_bound(it, sent, 1); };
+
+static_assert(HasLowerBoundIt<int*>);
+static_assert(!HasLowerBoundIt<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>);
+static_assert(!HasLowerBoundIt<ForwardIteratorNotDerivedFrom>);
+static_assert(!HasLowerBoundIt<ForwardIteratorNotIncrementable>);
+static_assert(!HasLowerBoundIt<NotLessThanComparable*>);
+
+template <class Range>
+concept HasLowerBoundR = requires(Range range) { std::ranges::lower_bound(range, 1); };
+
+static_assert(HasLowerBoundR<std::array<int, 1>>);
+static_assert(!HasLowerBoundR<ForwardRangeNotDerivedFrom>);
+static_assert(!HasLowerBoundR<ForwardRangeNotIncrementable>);
+static_assert(!HasLowerBoundR<UncheckedRange<NotLessThanComparable*>>);
+
+template <class Pred>
+concept HasLowerBoundPred = requires(int* it, Pred pred) {std::ranges::lower_bound(it, it, 1, pred); };
+
+static_assert(HasLowerBoundPred<std::ranges::less>);
+static_assert(!HasLowerBoundPred<IndirectUnaryPredicateNotCopyConstructible>);
+static_assert(!HasLowerBoundPred<IndirectUnaryPredicateNotPredicate>);
+
+template <class It>
+constexpr void test_iterators() {
+  { // simple test
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      std::same_as<It> auto ret = std::ranges::lower_bound(It(a), It(a + 6), 3);
+      assert(base(ret) == a + 2);
+    }
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      std::same_as<It> auto ret = std::ranges::lower_bound(range, 3);
+      assert(base(ret) == a + 2);
+    }
+  }
+
+  { // check that the predicate is used
+    {
+      int a[] = {6, 5, 4, 3, 2, 1};
+      auto ret = std::ranges::lower_bound(It(a), It(a + 6), 2, std::ranges::greater{});
+      assert(base(ret) == a + 4);
+    }
+    {
+      int a[] = {6, 5, 4, 3, 2, 1};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      auto ret = std::ranges::lower_bound(range, 2, std::ranges::greater{});
+      assert(base(ret) == a + 4);
+    }
+  }
+
+  { // check that the projection is used
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      auto ret = std::ranges::lower_bound(It(a), It(a + 6), 0, {}, [](int i) { return i - 3; });
+      assert(base(ret) == a + 2);
+    }
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      auto ret = std::ranges::lower_bound(range, 0, {}, [](int i) { return i - 3; });
+      assert(base(ret) == a + 2);
+    }
+  }
+
+  { // check that the last lower bound is returned
+    {
+      int a[] = {1, 2, 2, 2, 3};
+      auto ret = std::ranges::lower_bound(It(a), It(a + 5), 2);
+      assert(base(ret) == a + 1);
+    }
+    {
+      int a[] = {1, 2, 2, 2, 3};
+      auto range = std::ranges::subrange(It(a), It(a + 5));
+      auto ret = std::ranges::lower_bound(range, 2);
+      assert(base(ret) == a + 1);
+    }
+  }
+
+  { // check that end is returned if all elements compare less than
+    {
+      int a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::lower_bound(It(a), It(a + 4), 5);
+      assert(base(ret) == a + 4);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      auto range = std::ranges::subrange(It(a), It(a + 4));
+      auto ret = std::ranges::lower_bound(range, 5);
+      assert(base(ret) == a + 4);
+    }
+  }
+
+  { // check that the first element is returned if no element compares less than
+    {
+      int a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::lower_bound(It(a), It(a + 4), 0);
+      assert(base(ret) == a);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      auto range = std::ranges::subrange(It(a), It(a + 4));
+      auto ret = std::ranges::lower_bound(range, 0);
+      assert(base(ret) == a);
+    }
+  }
+
+  { // check that a single element works
+    {
+      int a[] = {1};
+      auto ret = std::ranges::lower_bound(It(a), It(a + 1), 1);
+      assert(base(ret) == a);
+    }
+    {
+      int a[] = {1};
+      auto range = std::ranges::subrange(It(a), It(a + 1));
+      auto ret = std::ranges::lower_bound(range, 1);
+      assert(base(ret) == a);
+    }
+  }
+
+  { // check that an even number of elements works
+    {
+      int a[] = {1, 3, 6, 6, 7, 8};
+      auto ret = std::ranges::lower_bound(It(a), It(a + 6), 6);
+      assert(base(ret) == a + 2);
+    }
+    {
+      int a[] = {1, 3, 6, 6, 7, 8};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      auto ret = std::ranges::lower_bound(range, 6);
+      assert(base(ret) == a + 2);
+    }
+  }
+
+  { // check that an odd number of elements works
+    {
+      int a[] = {1, 3, 6, 6, 7};
+      auto ret = std::ranges::lower_bound(It(a), It(a + 5), 6);
+      assert(base(ret) == a + 2);
+    }
+    {
+      int a[] = {1, 3, 6, 6, 7};
+      auto range = std::ranges::subrange(It(a), It(a + 5));
+      auto ret = std::ranges::lower_bound(range, 6);
+      assert(base(ret) == a + 2);
+    }
+  }
+
+  { // check that it works when all but the searched for element are equal
+    {
+      int a[] = {1, 6, 6, 6, 6, 6};
+      auto ret = std::ranges::lower_bound(It(a), It(a + 6), 1);
+      assert(base(ret) == a);
+    }
+    {
+      int a[] = {1, 6, 6, 6, 6, 6};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      auto ret = std::ranges::lower_bound(range, 1);
+      assert(base(ret) == a);
+    }
+  }
+}
+
+constexpr bool test() {
+  test_iterators<int*>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+
+  { // check that std::invoke is used for the projections
+    {
+      struct S { int check; int other; };
+      S a[] = {{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}};
+      auto ret = std::ranges::lower_bound(a, a + 6, 4, {}, &S::check);
+      assert(ret == a + 3);
+    }
+    {
+      struct S { int check; int other; };
+      S a[] = {{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}};
+      auto ret = std::ranges::lower_bound(a, 4, {}, &S::check);
+      assert(ret == a + 3);
+    }
+  }
+
+  { // check that std::invoke is used for the predicate
+    struct S {
+      int check;
+      int other;
+
+      constexpr bool compare(const S& s) const {
+        return check < s.check;
+      }
+    };
+    {
+      S a[] = {{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}};
+      auto ret = std::ranges::lower_bound(a, a + 6, S{4, 0}, &S::compare);
+      assert(ret == a + 3);
+    }
+    {
+      S a[] = {{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}};
+      auto ret = std::ranges::lower_bound(a, S{4, 0}, &S::compare);
+      assert(ret == a + 3);
+    }
+  }
+
+  { // check that an empty range works
+    {
+      std::array<int, 0> a;
+      auto ret = std::ranges::lower_bound(a.begin(), a.end(), 1);
+      assert(ret == a.end());
+    }
+    {
+      std::array<int, 0> a;
+      auto ret = std::ranges::lower_bound(a, 1);
+      assert(ret == a.end());
+    }
+  }
+
+  { // check that ranges::dangling is returned
+    [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret = std::ranges::lower_bound(std::array{1, 2}, 1);
+  }
+
+  { // check that an iterator is returned with a borrowing range
+    int a[] = {1, 2, 3};
+    std::same_as<int*> auto ret = std::ranges::lower_bound(std::views::all(a), 1);
+    assert(ret == a);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges.upper_bound.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+//          indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+//   constexpr I ranges::upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
+// template<forward_range R, class T, class Proj = identity,
+//          indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+//            ranges::less>
+//   constexpr borrowed_iterator_t<R>
+//     ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+struct NotLessThanComparable {};
+
+template <class It, class Sent = It>
+concept HasUpperBoundIt = requires(It it, Sent sent) { std::ranges::upper_bound(it, sent, 1); };
+
+static_assert(HasUpperBoundIt<int*>);
+static_assert(!HasUpperBoundIt<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>);
+static_assert(!HasUpperBoundIt<ForwardIteratorNotDerivedFrom>);
+static_assert(!HasUpperBoundIt<ForwardIteratorNotIncrementable>);
+static_assert(!HasUpperBoundIt<NotLessThanComparable*>);
+
+template <class Range>
+concept HasUpperBoundR = requires(Range range) { std::ranges::upper_bound(range, 1); };
+
+static_assert(HasUpperBoundR<std::array<int, 1>>);
+static_assert(!HasUpperBoundR<ForwardRangeNotDerivedFrom>);
+static_assert(!HasUpperBoundR<ForwardRangeNotIncrementable>);
+static_assert(!HasUpperBoundR<UncheckedRange<NotLessThanComparable*>>);
+
+template <class Pred>
+concept HasUpperBoundPred = requires(int* it, Pred pred) {std::ranges::upper_bound(it, it, 1, pred); };
+
+static_assert(HasUpperBoundPred<std::ranges::less>);
+static_assert(!HasUpperBoundPred<IndirectUnaryPredicateNotCopyConstructible>);
+static_assert(!HasUpperBoundPred<IndirectUnaryPredicateNotPredicate>);
+
+template <class It>
+constexpr void test_iterators() {
+  { // simple test
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      std::same_as<It> auto ret = std::ranges::upper_bound(It(a), It(a + 6), 3);
+      assert(base(ret) == a + 3);
+    }
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      std::same_as<It> auto ret = std::ranges::upper_bound(range, 3);
+      assert(base(ret) == a + 3);
+    }
+  }
+
+  { // check that the predicate is used
+    {
+      int a[] = {6, 5, 4, 3, 2, 1};
+      auto ret = std::ranges::upper_bound(It(a), It(a + 6), 2, std::ranges::greater{});
+      assert(base(ret) == a + 5);
+    }
+    {
+      int a[] = {6, 5, 4, 3, 2, 1};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      auto ret = std::ranges::upper_bound(range, 2, std::ranges::greater{});
+      assert(base(ret) == a + 5);
+    }
+  }
+
+  { // check that the projection is used
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      auto ret = std::ranges::upper_bound(It(a), It(a + 6), 0, {}, [](int i) { return i - 3; });
+      assert(base(ret) == a + 3);
+    }
+    {
+      int a[] = {1, 2, 3, 4, 5, 6};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      auto ret = std::ranges::upper_bound(range, 0, {}, [](int i) { return i - 3; });
+      assert(base(ret) == a + 3);
+    }
+  }
+
+  { // check that the last upper bound is returned
+    {
+      int a[] = {1, 2, 2, 2, 3};
+      auto ret = std::ranges::upper_bound(It(a), It(a + 5), 2);
+      assert(base(ret) == a + 4);
+    }
+    {
+      int a[] = {1, 2, 2, 2, 3};
+      auto range = std::ranges::subrange(It(a), It(a + 5));
+      auto ret = std::ranges::upper_bound(range, 2);
+      assert(base(ret) == a + 4);
+    }
+  }
+
+  { // check that end is returned if all elements compare less than
+    {
+      int a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::upper_bound(It(a), It(a + 4), 5);
+      assert(base(ret) == a + 4);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      auto range = std::ranges::subrange(It(a), It(a + 4));
+      auto ret = std::ranges::upper_bound(range, 5);
+      assert(base(ret) == a + 4);
+    }
+  }
+
+  { // check that the first element is returned if no element compares less than
+    {
+      int a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::upper_bound(It(a), It(a + 4), 0);
+      assert(base(ret) == a);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      auto range = std::ranges::subrange(It(a), It(a + 4));
+      auto ret = std::ranges::upper_bound(range, 0);
+      assert(base(ret) == a);
+    }
+  }
+
+  { // check that a single element works
+    {
+      int a[] = {1};
+      auto ret = std::ranges::upper_bound(It(a), It(a + 1), 1);
+      assert(base(ret) == a + 1);
+    }
+    {
+      int a[] = {1};
+      auto range = std::ranges::subrange(It(a), It(a + 1));
+      auto ret = std::ranges::upper_bound(range, 1);
+      assert(base(ret) == a + 1);
+    }
+  }
+
+  { // check that an even number of elements works
+    {
+      int a[] = {1, 3, 6, 6, 7, 8};
+      auto ret = std::ranges::upper_bound(It(a), It(a + 6), 6);
+      assert(base(ret) == a + 4);
+    }
+    {
+      int a[] = {1, 3, 6, 6, 7, 8};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      auto ret = std::ranges::upper_bound(range, 6);
+      assert(base(ret) == a + 4);
+    }
+  }
+
+  { // check that an odd number of elements works
+    {
+      int a[] = {1, 3, 6, 6, 7};
+      auto ret = std::ranges::upper_bound(It(a), It(a + 5), 6);
+      assert(base(ret) == a + 4);
+    }
+    {
+      int a[] = {1, 3, 6, 6, 7};
+      auto range = std::ranges::subrange(It(a), It(a + 5));
+      auto ret = std::ranges::upper_bound(range, 6);
+      assert(base(ret) == a + 4);
+    }
+  }
+
+  { // check that it works when all but the searched for element are equal
+    {
+      int a[] = {1, 6, 6, 6, 6, 6};
+      auto ret = std::ranges::upper_bound(It(a), It(a + 6), 1);
+      assert(base(ret) == a + 1);
+    }
+    {
+      int a[] = {1, 6, 6, 6, 6, 6};
+      auto range = std::ranges::subrange(It(a), It(a + 6));
+      auto ret = std::ranges::upper_bound(range, 1);
+      assert(base(ret) == a + 1);
+    }
+  }
+}
+
+constexpr bool test() {
+  test_iterators<int*>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+
+  { // check that std::invoke is used for the projections
+    {
+      struct S { int check; int other; };
+      S a[] = {{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}};
+      auto ret = std::ranges::upper_bound(a, a + 6, 4, {}, &S::check);
+      assert(ret == a + 4);
+    }
+    {
+      struct S { int check; int other; };
+      S a[] = {{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}};
+      auto ret = std::ranges::upper_bound(a, 4, {}, &S::check);
+      assert(ret == a + 4);
+    }
+  }
+
+  { // check that std::invoke is used for the predicate
+    struct S {
+      int check;
+      int other;
+
+      constexpr bool compare(const S& s) const {
+        return check < s.check;
+      }
+    };
+    {
+      S a[] = {{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}};
+      auto ret = std::ranges::upper_bound(a, a + 6, S{4, 0}, &S::compare);
+      assert(ret == a + 4);
+    }
+    {
+      S a[] = {{1, 6}, {2, 5}, {3, 4}, {4, 3}, {5, 2}, {6, 1}};
+      auto ret = std::ranges::upper_bound(a, S{4, 0}, &S::compare);
+      assert(ret == a + 4);
+    }
+  }
+
+  { // check that an empty range works
+    {
+      std::array<int, 0> a;
+      auto ret = std::ranges::upper_bound(a.begin(), a.end(), 1);
+      assert(ret == a.end());
+    }
+    {
+      std::array<int, 0> a;
+      auto ret = std::ranges::upper_bound(a, 1);
+      assert(ret == a.end());
+    }
+  }
+
+  { // check that ranges::dangling is returned
+    [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret = std::ranges::upper_bound(std::array{1, 2}, 1);
+  }
+
+  { // check that an iterator is returned with a borrowing range
+    int a[] = {1, 2, 3};
+    std::same_as<int*> auto ret = std::ranges::upper_bound(std::views::all(a), 1);
+    assert(ret == a + 1);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 //auto plus = [](int x, int y) { return x == y; };
 //std::mt19937 g;
 
 // [algorithm.syn]
 
 //static_assert(test(std::ranges::adjacent_find, a));
 //static_assert(test(std::ranges::all_of, a, odd));
 //static_assert(test(std::ranges::any_of, a, odd));
-//static_assert(test(std::ranges::binary_search, a, 42));
+static_assert(test(std::ranges::binary_search, a, 42));
 //static_assert(test(std::ranges::clamp, 42, 42, 42));
 //static_assert(test(std::ranges::copy, a, a));
 //static_assert(test(std::ranges::copy_backward, a, a));
 //static_assert(test(std::ranges::copy_if, a, a, odd));
 //static_assert(test(std::ranges::copy_n, a, 10, a));
 static_assert(test(std::ranges::count, a, 42));
 static_assert(test(std::ranges::count_if, a, odd));
 //static_assert(test(std::ranges::ends_with, a, a));

 //static_assert(test(std::ranges::inplace_merge, a, a+5));
 //static_assert(test(std::ranges::is_heap, a));
 //static_assert(test(std::ranges::is_heap_until, a));
 //static_assert(test(std::ranges::is_partitioned, a, odd));
 //static_assert(test(std::ranges::is_permutation, a, a));
 //static_assert(test(std::ranges::is_sorted, a));
 //static_assert(test(std::ranges::is_sorted_until, a));
 //static_assert(test(std::ranges::lexicographical_compare, a, a));
-//static_assert(test(std::ranges::lower_bound, a, 42));
+static_assert(test(std::ranges::lower_bound, a, 42));
 //static_assert(test(std::ranges::make_heap, a));
 //static_assert(test(std::ranges::max, a));
 static_assert(test(std::ranges::max_element, a));
 //static_assert(test(std::ranges::merge, a, a, a));
 static_assert(test(std::ranges::min, a));
 static_assert(test(std::ranges::min_element, a));
 static_assert(test(std::ranges::minmax, a));
 static_assert(test(std::ranges::minmax_element, a));

 //static_assert(test(std::ranges::sort_heap, a));
 //static_assert(test(std::ranges::stable_partition, a, odd));
 //static_assert(test(std::ranges::stable_sort, a));
 //static_assert(test(std::ranges::starts_with, a, a));
 static_assert(test(std::ranges::swap_ranges, a, a));
 //static_assert(test(std::ranges::transform, a, a, triple));
 //static_assert(test(std::ranges::unique, a));
 //static_assert(test(std::ranges::unique_copy, a, a));
-//static_assert(test(std::ranges::upper_bound, a, 42));
+static_assert(test(std::ranges::upper_bound, a, 42));
 
 // [memory.syn]
 
 static_assert(test(std::ranges::construct_at, a, 42));
 static_assert(test(std::ranges::destroy, a));
 static_assert(test(std::ranges::destroy, a, a+10));
 static_assert(test(std::ranges::destroy_at, a));
 static_assert(test(std::ranges::destroy_n, a, 10));

libcxx/test/support/almost_satisfies_types.h

public:
   WeaklyIncrementableNotMovable& operator++();
   void operator++(int);
   WeaklyIncrementableNotMovable(const WeaklyIncrementableNotMovable&) = delete;
 };
 
 static_assert(!std::movable<WeaklyIncrementableNotMovable>);
 static_assert(!std::weakly_incrementable<WeaklyIncrementableNotMovable>);
 
+// almost a forward_iterator
+class ForwardIteratorNotDerivedFrom {
+public:
+  using difference_type = long;
+  using value_type = int;
+  using iterator_category = std::input_iterator_tag;
+
+  ForwardIteratorNotDerivedFrom& operator++();
+  ForwardIteratorNotDerivedFrom operator++(int);
+  const int& operator*() const;
+  bool operator==(const ForwardIteratorNotDerivedFrom&) const = default;
+};
+
+using ForwardRangeNotDerivedFrom = UncheckedRange<ForwardIteratorNotDerivedFrom>;
+
+static_assert(std::input_iterator<ForwardIteratorNotDerivedFrom>);
+static_assert(std::incrementable<ForwardIteratorNotDerivedFrom>);
+static_assert(std::sentinel_for<ForwardIteratorNotDerivedFrom, ForwardIteratorNotDerivedFrom>);
+static_assert(!std::forward_iterator<ForwardIteratorNotDerivedFrom>);
+
+class ForwardIteratorNotIncrementable {
+public:
+  using difference_type = long;
+  using value_type = int;
+  using iterator_category = std::forward_iterator_tag;
+
+  ForwardIteratorNotIncrementable& operator++();
+  int operator++(int);
+  const int& operator*() const;
+  bool operator==(const ForwardIteratorNotIncrementable&) const = default;
+};
+
+using ForwardRangeNotIncrementable = UncheckedRange<ForwardIteratorNotIncrementable>;
+
+static_assert(std::input_iterator<ForwardIteratorNotIncrementable>);
+static_assert(!std::incrementable<ForwardIteratorNotIncrementable>);
+static_assert(std::sentinel_for<ForwardIteratorNotIncrementable, ForwardIteratorNotIncrementable>);
+static_assert(!std::forward_iterator<ForwardIteratorNotIncrementable>);
+
 #endif // ALMOST_SATISFIES_TYPES_H