tmp/tmpw6gy_9fq/{from.md → to.md}
RENAMED
|
@@ -1,16 +1,18 @@
|
|
| 1 |
### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
|
| 2 |
|
| 3 |
-
|
| 4 |
-
|
| 5 |
-
|
| 6 |
-
|
| 7 |
-
|
| 8 |
-
|
| 9 |
-
|
| 10 |
-
|
| 11 |
-
number of steps
|
|
|
|
|
|
|
| 12 |
|
| 13 |
#### `lower_bound` <a id="lower.bound">[[lower.bound]]</a>
|
| 14 |
|
| 15 |
``` cpp
|
| 16 |
template<class ForwardIterator, class T>
|
|
|
|
| 1 |
### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
|
| 2 |
|
| 3 |
+
#### General <a id="alg.binary.search.general">[[alg.binary.search.general]]</a>
|
| 4 |
+
|
| 5 |
+
All of the algorithms in [[alg.binary.search]] are versions of binary
|
| 6 |
+
search and assume that the sequence being searched is partitioned with
|
| 7 |
+
respect to an expression formed by binding the search key to an argument
|
| 8 |
+
of the comparison function. They work on non-random access iterators
|
| 9 |
+
minimizing the number of comparisons, which will be logarithmic for all
|
| 10 |
+
types of iterators. They are especially appropriate for random access
|
| 11 |
+
iterators, because these algorithms do a logarithmic number of steps
|
| 12 |
+
through the data structure. For non-random access iterators they execute
|
| 13 |
+
a linear number of steps.
|
| 14 |
|
| 15 |
#### `lower_bound` <a id="lower.bound">[[lower.bound]]</a>
|
| 16 |
|
| 17 |
``` cpp
|
| 18 |
template<class ForwardIterator, class T>
|