Binary search algorithm for distinct

tim-harding · Sep 6, 2023 · c47a743 · c47a743
1 parent 9af72fb
commit c47a743
Showing 1 changed file with 11 additions and 24 deletions.
diff --git a/src/solutions/_08_recursion_and_dynamic_programming/_03_magic_index.rs b/src/solutions/_08_recursion_and_dynamic_programming/_03_magic_index.rs
@@ -5,7 +5,17 @@ pub struct Solution;
 
 impl MagicIndex for Solution {
     fn magic_index_distinct(array: &[i64]) -> Option<usize> {
-        Self::magic_index_inner(array, 0, array.len() - 1)
+        let mut left = 0;
+        let mut right = array.len();
+        while left < right {
+            let mid = left + (right - left) / 2;
+            match array[mid].cmp(&(mid as i64)) {
+                Ordering::Less => left = mid + 1,
+                Ordering::Equal => return Some(mid),
+                Ordering::Greater => right = mid,
+            }
+        }
+        None
     }
 
     fn magic_index_indistinct(array: &[i64]) -> Option<usize> {
@@ -16,26 +26,3 @@ impl MagicIndex for Solution {
             .map(|(i, _)| i)
     }
 }
-
-impl Solution {
-    fn magic_index_inner(array: &[i64], left: usize, right: usize) -> Option<usize> {
-        if right <= left {
-            return None;
-        }
-
-        match (
-            array[left].cmp(&(left as i64)),
-            array[right].cmp(&(right as i64)),
-        ) {
-            // Can't find the magic index if the subarray does not contain it
-            (Ordering::Less, Ordering::Less) | (Ordering::Greater, Ordering::Greater) => None,
-            (Ordering::Equal, _) => Some(left),
-            (_, Ordering::Equal) => Some(right),
-            (Ordering::Less, Ordering::Greater) | (Ordering::Greater, Ordering::Less) => {
-                let mid = left + (right - left) / 2;
-                Self::magic_index_inner(array, left, mid)
-                    .or_else(|| Self::magic_index_inner(array, mid + 1, right))
-            }
-        }
-    }
-}