chromium / external / github.com / dart-lang / collection / 69766daafbaa8535d1343fb7cd87e713f57c107f^! / .

commit | 69766daafbaa8535d1343fb7cd87e713f57c107f | [log] [tgz] |
---|---|---|

author | Nate Bosch <nbosch@google.com> | Wed May 25 14:52:34 2022 |

committer | GitHub <noreply@github.com> | Wed May 25 14:52:34 2022 |

tree | f3305b9a78821e25e6653b7a747495687d235540 | |

parent | 5b43ad7779e9b68101a61e90c54211ddee3b8a6d [diff] |

Add complexity bound on binary search methods (#239) Closes #237 In each of the list extensions that mention "Uses binary search" add a sentence documenting that the search takes `log(n)` comparisons. Add a sentence about using binary search and the runtime to the top level algorithm methods.

diff --git a/CHANGELOG.md b/CHANGELOG.md index 6161476..806a8b0 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md

@@ -1,3 +1,5 @@ +## 1.16.1-dev + ## 1.16.0 * Add an `Iterable.slices` extension method.

diff --git a/lib/src/algorithms.dart b/lib/src/algorithms.dart index 820d32b..eb9e1de 100644 --- a/lib/src/algorithms.dart +++ b/lib/src/algorithms.dart

@@ -57,6 +57,8 @@ /// Returns the first position in [sortedList] that does not compare less than /// [value]. /// +/// Uses binary search to find the location of [value]. +/// This takes on the order of `log(n)` comparisons. /// If the list isn't sorted according to the [compare] function, the result /// is unpredictable. /// @@ -72,6 +74,8 @@ /// Returns the first position in [sortedList] that is not before [value]. /// +/// Uses binary search to find the location of [value]. +/// This takes on the order of `log(n)` comparisons. /// Elements are compared using the [compare] function of the [keyOf] property of /// the elements. /// If the list isn't sorted according to this order, the result is unpredictable.

diff --git a/lib/src/list_extensions.dart b/lib/src/list_extensions.dart index 43d1ef3..4d6ae3f 100644 --- a/lib/src/list_extensions.dart +++ b/lib/src/list_extensions.dart

@@ -16,6 +16,7 @@ /// Returns the index of [element] in this sorted list. /// /// Uses binary search to find the location of [element]. + /// This takes on the order of `log(n)` comparisons. /// The list *must* be sorted according to [compare], /// otherwise the result is unspecified /// @@ -26,6 +27,7 @@ /// Returns the index of [element] in this sorted list. /// /// Uses binary search to find the location of [element]. + /// This takes on the order of `log(n)` comparisons. /// The list *must* be sorted according to [compare] on the [keyOf] of elements, /// otherwise the result is unspecified. /// @@ -42,6 +44,7 @@ /// Returns the index of [element] in this sorted list. /// /// Uses binary search to find the location of [element]. + /// This takes on the order of `log(n)` comparisons. /// The list *must* be sorted according to the natural ordering of /// the [keyOf] of elements, otherwise the result is unspecified. /// @@ -57,6 +60,7 @@ /// Returns the index where [element] should be in this sorted list. /// /// Uses binary search to find the location of [element]. + /// This takes on the order of `log(n)` comparisons. /// The list *must* be sorted according to [compare], /// otherwise the result is unspecified. /// @@ -71,6 +75,7 @@ /// Returns the index where [element] should be in this sorted list. /// /// Uses binary search to find the location of [element]. + /// This takes on the order of `log(n)` comparisons. /// The list *must* be sorted according to [compare] of /// the [keyOf] of the elements, otherwise the result is unspecified. /// @@ -90,6 +95,7 @@ /// Returns the index where [element] should be in this sorted list. /// /// Uses binary search to find the location of [element]. + /// This takes on the order of `log(n)` comparisons. /// The list *must* be sorted according to the /// natural ordering of the [keyOf] of the elements, /// otherwise the result is unspecified. @@ -276,6 +282,7 @@ /// Returns the index of [element] in this sorted list. /// /// Uses binary search to find the location of [element]. + /// This takes on the order of `log(n)` comparisons. /// The list *must* be sorted according to [compare], /// otherwise the result is unspecified. /// If [compare] is omitted, it uses the natural order of the elements. @@ -288,6 +295,7 @@ /// Returns the index where [element] should be in this sorted list. /// /// Uses binary search to find the location of where [element] should be. + /// This takes on the order of `log(n)` comparisons. /// The list *must* be sorted according to [compare], /// otherwise the result is unspecified. /// If [compare] is omitted, it uses the natural order of the elements.

diff --git a/pubspec.yaml b/pubspec.yaml index ae623b8..436a1e1 100644 --- a/pubspec.yaml +++ b/pubspec.yaml

@@ -1,5 +1,5 @@ name: collection -version: 1.16.0 +version: 1.16.1-dev description: Collections and utilities functions and classes related to collections. repository: https://github.com/dart-lang/collection