From e7e054e21fd530fa6873b7aedd1fc4d4cfe5eb29 Mon Sep 17 00:00:00 2001
From: Federico Igne <git@federicoigne.com>
Date: Sat, 2 Jan 2021 17:58:32 +0000
Subject: [rust] Binary Search

---
 rust/binary-search/src/lib.rs | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
 create mode 100644 rust/binary-search/src/lib.rs

(limited to 'rust/binary-search/src/lib.rs')

diff --git a/rust/binary-search/src/lib.rs b/rust/binary-search/src/lib.rs
new file mode 100644
index 0000000..dc80137
--- /dev/null
+++ b/rust/binary-search/src/lib.rs
@@ -0,0 +1,16 @@
+pub fn find<T: Ord, C: AsRef<[T]>>(array: C, key: T) -> Option<usize> {
+    let array = array.as_ref();
+    match array.len() {
+        0 => None,
+        1 => Some(0).filter(|_| array[0] == key),
+        n => {
+            let mid = n / 2;
+            let (a1, a2) = array.split_at(mid);
+            if key < array[mid] {
+                find(a1, key)
+            } else {
+                find(a2, key).map(|i| i + mid)
+            }
+        }
+    }
+}
-- 
cgit v1.2.3