Auto merge of #30917 - arthurprs:bs_bounds_check, r=alexcrichton

Avoid bounds checking for binary search. All calculated indexes are safe and the branch is useless.

1 files changed, 12 insertions, 11 deletions

diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index 6107564b4ae..40041c748e7 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -294,22 +294,23 @@ impl<T> SliceExt for [T] {
     fn binary_search_by<F>(&self, mut f: F) -> Result<usize, usize> where
         F: FnMut(&T) -> Ordering
     {
-        let mut base : usize = 0;
-        let mut lim : usize = self.len();
+        let mut base = 0usize;
+        let mut s = self;
 
-        while lim != 0 {
-            let ix = base + (lim >> 1);
-            match f(&self[ix]) {
-                Equal => return Ok(ix),
+        loop {
+            let (head, tail) = s.split_at(s.len() >> 1);
+            if tail.is_empty() {
+                return Err(base)
+            }
+            match f(&tail[0]) {
                 Less => {
-                    base = ix + 1;
-                    lim -= 1;
+                    base += head.len() + 1;
+                    s = &tail[1..];
                 }
-                Greater => ()
+                Greater => s = head,
+                Equal => return Ok(base + head.len()),
             }
-            lim >>= 1;
         }
-        Err(base)
     }
 
     #[inline]