Fix some confusing wording and improve slice-search-related docs

3 files changed, 35 insertions, 11 deletions

diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs
index d81f24e7202..736b38370ab 100644
--- a/library/alloc/src/collections/linked_list.rs
+++ b/library/alloc/src/collections/linked_list.rs
@@ -645,7 +645,7 @@ impl<T> LinkedList<T> {
     /// Returns `true` if the `LinkedList` contains an element equal to the
     /// given value.
     ///
-    /// This operation should compute in *O*(*n*) time.
+    /// This operation should compute linearly in *O*(*n*) time.
     ///
     /// # Examples
     ///
@@ -1569,7 +1569,7 @@ impl<'a, T> CursorMut<'a, T> {
     /// Appends an element to the front of the cursor's parent list. The node
     /// that the cursor points to is unchanged, even if it is the "ghost" node.
     ///
-    /// This operation should compute in O(1) time.
+    /// This operation should compute in *O*(1) time.
     // `push_front` continues to point to "ghost" when it addes a node to mimic
     // the behavior of `insert_before` on an empty list.
     #[unstable(feature = "linked_list_cursors", issue = "58533")]
@@ -1584,7 +1584,7 @@ impl<'a, T> CursorMut<'a, T> {
     /// Appends an element to the back of the cursor's parent list. The node
     /// that the cursor points to is unchanged, even if it is the "ghost" node.
     ///
-    /// This operation should compute in O(1) time.
+    /// This operation should compute in *O*(1) time.
     #[unstable(feature = "linked_list_cursors", issue = "58533")]
     pub fn push_back(&mut self, elt: T) {
         // Safety: We know that `push_back` does not change the position in
@@ -1603,7 +1603,7 @@ impl<'a, T> CursorMut<'a, T> {
     /// unchanged, unless it was pointing to the front element. In that case, it
     /// points to the new front element.
     ///
-    /// This operation should compute in O(1) time.
+    /// This operation should compute in *O*(1) time.
     #[unstable(feature = "linked_list_cursors", issue = "58533")]
     pub fn pop_front(&mut self) -> Option<T> {
         // We can't check if current is empty, we must check the list directly.
@@ -1630,7 +1630,7 @@ impl<'a, T> CursorMut<'a, T> {
     /// unchanged, unless it was pointing to the back element. In that case, it
     /// points to the "ghost" element.
     ///
-    /// This operation should compute in O(1) time.
+    /// This operation should compute in *O*(1) time.
     #[unstable(feature = "linked_list_cursors", issue = "58533")]
     pub fn pop_back(&mut self) -> Option<T> {
         if self.list.is_empty() {
diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs
index 7139a0fb94d..33b98389702 100644
--- a/library/alloc/src/collections/vec_deque/mod.rs
+++ b/library/alloc/src/collections/vec_deque/mod.rs
@@ -1322,6 +1322,12 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// Returns `true` if the deque contains an element equal to the
     /// given value.
     ///
+    /// This operation is *O*(*n*).
+    ///
+    /// Note that if you have a sorted `VecDeque`, [`binary_search`] may be faster.
+    ///
+    /// [`binary_search`]: VecDeque::binary_search
+    ///
     /// # Examples
     ///
     /// ```
@@ -2528,7 +2534,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
         }
     }
 
-    /// Binary searches the sorted deque for a given element.
+    /// Binary searches this `VecDeque` for a given element.
+    /// This behaves similarly to [`contains`] if this `VecDeque` is sorted.
     ///
     /// If the value is found then [`Result::Ok`] is returned, containing the
     /// index of the matching element. If there are multiple matches, then any
@@ -2538,6 +2545,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     ///
     /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`].
     ///
+    /// [`contains`]: VecDeque::contains
     /// [`binary_search_by`]: VecDeque::binary_search_by
     /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
     /// [`partition_point`]: VecDeque::partition_point
@@ -2581,7 +2589,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
         self.binary_search_by(|e| e.cmp(x))
     }
 
-    /// Binary searches the sorted deque with a comparator function.
+    /// Binary searches this `VecDeque` with a comparator function.
+    /// This behaves similarly to [`contains`] if this `VecDeque` is sorted.
     ///
     /// The comparator function should implement an order consistent
     /// with the sort order of the deque, returning an order code that
@@ -2596,6 +2605,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     ///
     /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`].
     ///
+    /// [`contains`]: VecDeque::contains
     /// [`binary_search`]: VecDeque::binary_search
     /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
     /// [`partition_point`]: VecDeque::partition_point
@@ -2634,7 +2644,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
         }
     }
 
-    /// Binary searches the sorted deque with a key extraction function.
+    /// Binary searches this `VecDeque` with a key extraction function.
+    /// This behaves similarly to [`contains`] if this `VecDeque` is sorted.
     ///
     /// Assumes that the deque is sorted by the key, for instance with
     /// [`make_contiguous().sort_by_key()`] using the same key extraction function.
@@ -2647,6 +2658,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     ///
     /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`].
     ///
+    /// [`contains`]: VecDeque::contains
     /// [`make_contiguous().sort_by_key()`]: VecDeque::make_contiguous
     /// [`binary_search`]: VecDeque::binary_search
     /// [`binary_search_by`]: VecDeque::binary_search_by
diff --git a/library/core/src/slice/mod.rs b/library/core/src/slice/mod.rs
index cd38c3a7547..d68982d18e0 100644
--- a/library/core/src/slice/mod.rs
+++ b/library/core/src/slice/mod.rs
@@ -2095,6 +2095,12 @@ impl<T> [T] {
 
     /// Returns `true` if the slice contains an element with the given value.
     ///
+    /// This operation is *O*(*n*).
+    ///
+    /// Note that if you have a sorted slice, [`binary_search`] may be faster.
+    ///
+    /// [`binary_search`]: slice::binary_search
+    ///
     /// # Examples
     ///
     /// ```
@@ -2251,7 +2257,8 @@ impl<T> [T] {
         None
     }
 
-    /// Binary searches this sorted slice for a given element.
+    /// Binary searches this slice for a given element.
+    /// This behaves similary to [`contains`] if this slice is sorted.
     ///
     /// If the value is found then [`Result::Ok`] is returned, containing the
     /// index of the matching element. If there are multiple matches, then any
@@ -2263,6 +2270,7 @@ impl<T> [T] {
     ///
     /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`].
     ///
+    /// [`contains`]: slice::contains
     /// [`binary_search_by`]: slice::binary_search_by
     /// [`binary_search_by_key`]: slice::binary_search_by_key
     /// [`partition_point`]: slice::partition_point
@@ -2301,7 +2309,8 @@ impl<T> [T] {
         self.binary_search_by(|p| p.cmp(x))
     }
 
-    /// Binary searches this sorted slice with a comparator function.
+    /// Binary searches this slice with a comparator function.
+    /// This behaves similarly to [`contains`] if this slice is sorted.
     ///
     /// The comparator function should implement an order consistent
     /// with the sort order of the underlying slice, returning an
@@ -2318,6 +2327,7 @@ impl<T> [T] {
     ///
     /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`].
     ///
+    /// [`contains`]: slice::contains
     /// [`binary_search`]: slice::binary_search
     /// [`binary_search_by_key`]: slice::binary_search_by_key
     /// [`partition_point`]: slice::partition_point
@@ -2376,7 +2386,8 @@ impl<T> [T] {
         Err(left)
     }
 
-    /// Binary searches this sorted slice with a key extraction function.
+    /// Binary searches this slice with a key extraction function.
+    /// This behaves similarly to [`contains`] if this slice is sorted.
     ///
     /// Assumes that the slice is sorted by the key, for instance with
     /// [`sort_by_key`] using the same key extraction function.
@@ -2391,6 +2402,7 @@ impl<T> [T] {
     ///
     /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`].
     ///
+    /// [`contains`]: slice::contains
     /// [`sort_by_key`]: slice::sort_by_key
     /// [`binary_search`]: slice::binary_search
     /// [`binary_search_by`]: slice::binary_search_by