1 files changed, 30 insertions, 0 deletions

diff --git a/crates/stdx/src/lib.rs b/crates/stdx/src/lib.rs
index 988853ed2..ea0e6b949 100644
--- a/crates/stdx/src/lib.rs
+++ b/crates/stdx/src/lib.rs
@@ -158,6 +158,36 @@ impl<'a> Iterator for LinesWithEnds<'a> {
     }
 }
 
+// https://github.com/rust-lang/rust/issues/73831
+pub fn partition_point<T, P>(slice: &[T], mut pred: P) -> usize
+where
+    P: FnMut(&T) -> bool,
+{
+    let mut left = 0;
+    let mut right = slice.len();
+
+    while left != right {
+        let mid = left + (right - left) / 2;
+        // SAFETY:
+        // When left < right, left <= mid < right.
+        // Therefore left always increases and right always decreases,
+        // and either of them is selected.
+        // In both cases left <= right is satisfied.
+        // Therefore if left < right in a step,
+        // left <= right is satisfied in the next step.
+        // Therefore as long as left != right, 0 <= left < right <= len is satisfied
+        // and if this case 0 <= mid < len is satisfied too.
+        let value = unsafe { slice.get_unchecked(mid) };
+        if pred(value) {
+            left = mid + 1;
+        } else {
+            right = mid;
+        }
+    }
+
+    left
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;