[rust] Binary Search

1 files changed, 16 insertions, 0 deletions

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)
+            }
+        }
+    }
+}