1 files changed, 18 insertions, 16 deletions
diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index 5039bef631e..e5b4df96845 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -394,23 +394,25 @@ impl<T> SliceExt for [T] {
     fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
         where F: FnMut(&'a T) -> Ordering
     {
-        let mut base = 0usize;
-        let mut s = self;
-
-        loop {
-            let (head, tail) = s.split_at(s.len() >> 1);
-            if tail.is_empty() {
-                return Err(base)
-            }
-            match f(&tail[0]) {
-                Less => {
-                    base += head.len() + 1;
-                    s = &tail[1..];
-                }
-                Greater => s = head,
-                Equal => return Ok(base + head.len()),
-            }
+        let s = self;
+        let mut size = s.len();
+        if size == 0 {
+            return Err(0);
         }
+        let mut base = 0usize;
+        while size > 1 {
+            let half = size / 2;
+            let mid = base + half;
+            // mid is always in [0, size).
+            // mid >= 0: by definition
+            // mid < size: mid = size / 2 + size / 4 + size / 8 ...
+            let cmp = f(unsafe { s.get_unchecked(mid) });
+            base = if cmp == Greater { base } else { mid };
+            size -= half;
+        }
+        // base is always in [0, size) because base <= mid.
+        let cmp = f(unsafe { s.get_unchecked(base) });
+        if cmp == Equal { Ok(base) } else { Err(base + (cmp == Less) as usize) }
     }
 
     #[inline]