From Jason Turner

[binary.search]

C++17 → C++20 2.7 KB 48 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpzawwqeoq/{from.md → to.md} +31 -14
tmp/tmpzawwqeoq/{from.md → to.md} RENAMED
@@ -1,25 +1,42 @@
1
  #### `binary_search` <a id="binary.search">[[binary.search]]</a>
2
 
3
  ``` cpp
4
  template<class ForwardIterator, class T>
5
- bool binary_search(ForwardIterator first, ForwardIterator last,
 
6
  const T& value);
7
 
8
  template<class ForwardIterator, class T, class Compare>
9
- bool binary_search(ForwardIterator first, ForwardIterator last,
 
10
  const T& value, Compare comp);
 
 
 
 
 
 
 
 
 
 
11
  ```
12
 
13
- *Requires:* The elements `e` of \[`first`, `last`) are partitioned with
14
- respect to the expressions `e < value` and `!(value < e)` or
15
- `comp(e, value)` and `!comp(value, e)`. Also, for all elements `e` of
16
- `[first, last)`, `e < value` implies `!(value < e)` or `comp(e, value)`
17
- implies `!comp(value, e)`.
18
-
19
- *Returns:* `true` if there is an iterator `i` in the range \[`first`,
20
- `last`) that satisfies the corresponding conditions:
21
- `!(*i < value) && !(value < *i)` or
22
- `comp(*i, value) == false && comp(value, *i) == false`.
23
-
24
- *Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 
 
 
 
 
25
 
 
1
  #### `binary_search` <a id="binary.search">[[binary.search]]</a>
2
 
3
  ``` cpp
4
  template<class ForwardIterator, class T>
5
+ constexpr bool
6
+ binary_search(ForwardIterator first, ForwardIterator last,
7
  const T& value);
8
 
9
  template<class ForwardIterator, class T, class Compare>
10
+ constexpr bool
11
+ binary_search(ForwardIterator first, ForwardIterator last,
12
  const T& value, Compare comp);
13
+
14
+ template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
15
+ indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
16
+ constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {},
17
+ Proj proj = {});
18
+ template<forward_range R, class T, class Proj = identity,
19
+ indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
20
+ ranges::less>
21
+ constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {},
22
+ Proj proj = {});
23
  ```
24
 
25
+ Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
26
+ parameters by those names.
27
+
28
+ *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
29
+ with respect to the expressions
30
+ `bool(invoke(comp, invoke(proj, e), value))` and
31
+ `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
32
+ `e` of `[first, last)`, `bool(comp(e, value))` implies
33
+ `!bool(comp(value, e))` for the overloads in namespace `std`.
34
+
35
+ *Returns:* `true` if and only if for some iterator `i` in the range
36
+ \[`first`, `last`),
37
+ `!bool(invoke(comp, invoke(proj, *i), value)) && !bool(invoke(comp, value, invoke(proj, *i)))`
38
+ is `true`.
39
+
40
+ *Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons and
41
+ projections.
42