moonbitlang · peter-jerry-ye · Jul 1, 2025 · Jun 30, 2025 · Jun 30, 2025 · Jun 30, 2025
diff --git a/deque/deque.mbt b/deque/deque.mbt
@@ -1423,3 +1423,138 @@ pub fn[A] T::drain(self : T[A], start~ : Int, len? : Int) -> T[A] {
   self.len -= len
   deque
 }
+
+///|
+/// Performs a binary search on a sorted deque using a custom comparison function.
+/// Returns the position of the matching element if found, or the position where
+/// the element could be inserted while maintaining the sorted order.
+///
+/// Parameters:
+///
+/// * `comparator` : A function that compares each element with the target value,
+/// returning:
+///  * A negative integer if the element is less than the target
+///  * Zero if the element equals the target
+///  * A positive integer if the element is greater than the target
+///
+/// Returns a `Result` containing either:
+///
+/// * `Ok(index)` if a matching element is found at position `index`
+/// * `Err(index)` if no match is found, where `index` is the position where the
+/// element could be inserted
+///
+/// Example:
+///
+/// ```moonbit
+/// let dq = @deque.of([1, 3, 5, 7, 9])
+///
+/// 
+/// let find_3 = dq.binary_search_by(fn(x) {
+///   if x < 3 {
+///     -1
+///   } else if x > 3 {
+///     1
+///   } else {
+///     0
+///   }
+/// })
+/// inspect(find_3, content="Ok(1)")
+///
+/// 
+/// let find_4 = dq.binary_search_by(fn(x) {
+///   if x < 4 {
+///     -1
+///   } else if x > 4 {
+///     1
+///   } else {
+///     0
+///   }
+/// })
+/// inspect(find_4, content="Err(2)")
+/// ```
+///
+/// Notes:
+///
+/// * Assumes the deque is sorted according to the ordering implied by the
+/// comparison function
+/// * For multiple matches, returns the leftmost matching position
+/// * Returns an insertion point that maintains the sort order when no match is
+/// found
+/// * Handles the deque's ring buffer structure internally
+/// * For empty deques, returns `Err(0)`
+#locals(cmp)
+pub fn[A] binary_search_by(self : T[A], cmp : (A) -> Int) -> Result[Int, Int] {
+  let len = self.len
+  let mut i = 0
+  let mut j = len
+  while i < j {
+    let h = i + (j - i) / 2
+    match self.get(h) {
+      Some(element) =>
+        match cmp(element) {
+          -1 => i = h + 1 // Continue searching right
+          1 => j = h // Continue searching left
+          _ => { // Found match, find leftmost
+            j = h
+            while i < j {
+              let mid = i + (j - i) / 2
+              match self.get(mid) {
+                Some(v) =>
+                  match cmp(v) {
+                    0 => j = mid
+                    _ => i = mid + 1
+                  }
+                None => break
+              }
+            }
+            return Ok(i)
+          }
+        }
+      None => return Err(i)
+    }
+  }
+  Err(i)
+}
+
+///|
+/// Safe element access with bounds checking
+pub fn[A] get(self : T[A], index : Int) -> A? {
+  if index >= 0 && index < self.len {
+    let physical_index = (self.head + index) % self.buf.length()
+    Some(self.buf[physical_index])
+  } else {
+    None
+  }
+}
+
+///|
+/// Performs a binary search on a sorted deque for the given value.
+/// Returns the position of the value if found, or the position where
+/// the value could be inserted while maintaining the sorted order.
+///
+/// Parameters:
+///
+/// * `value` : The value to search for in the deque
+///
+/// Returns a `Result` containing either:
+///
+/// * `Ok(index)` if the value is found at position `index`
+/// * `Err(index)` if the value is not found, where `index` is the
+///   position where the value could be inserted
+///
+/// Example:
+///
+/// ```moonbit
+/// let dq = @deque.of([1, 3, 5, 7, 9])
+/// let result = dq.binary_search(5)
+/// inspect(result, content="Ok(2)")
+/// ```
+///
+/// Notes:
+///
+/// * Assumes the deque is sorted in ascending order
+/// * For multiple matches, returns the leftmost matching position
+/// * Returns an insertion point that maintains the sort order when no match is found
+pub fn[A : Compare] binary_search(self : T[A], value : A) -> Result[Int, Int] {
+  self.binary_search_by(fn(x) { x.compare(value) })
+}
diff --git a/deque/deque.mbti b/deque/deque.mbti
@@ -18,6 +18,8 @@ fn[A] of(FixedArray[A]) -> T[A]
 type T[A]
 fn[A] T::as_views(Self[A]) -> (ArrayView[A], ArrayView[A])
 fn[A] T::back(Self[A]) -> A?
+fn[A : Compare] T::binary_search(Self[A], A) -> Result[Int, Int]
+fn[A] T::binary_search_by(Self[A], (A) -> Int) -> Result[Int, Int]
 fn[A] T::capacity(Self[A]) -> Int
 fn[A] T::clear(Self[A]) -> Unit
 fn[A : Eq] T::contains(Self[A], A) -> Bool
@@ -29,6 +31,7 @@ fn[A] T::eachi(Self[A], (Int, A) -> Unit) -> Unit
 fn[A] T::filter_map_inplace(Self[A], (A) -> A?) -> Unit
 fn[A] T::flatten(Self[Self[A]]) -> Self[A]
 fn[A] T::front(Self[A]) -> A?
+fn[A] T::get(Self[A], Int) -> A?
 fn[A] T::is_empty(Self[A]) -> Bool
 fn[A] T::iter(Self[A]) -> Iter[A]
 fn[A] T::iter2(Self[A]) -> Iter2[Int, A]

diff --git a/deque/deque_test.mbt b/deque/deque_test.mbt
@@ -1048,3 +1048,109 @@ test "drain when wrapped around" {
   inspect(dq.as_views(), content="([1, 2, 3, 6], [])")
   inspect(dq2, content="@deque.of([4, 5])")
 }
+
+///|
+test "binary_search_by on multiple elements deque" {
+  let dq = @deque.of([1, 3, 5, 7, 9])
+
+  // Find the element that exists (the first one)
+  let found_first = dq.binary_search_by(fn(x) { x.compare(1) })
+  inspect(found_first, content="Ok(0)")
+
+  // Find the element that exists (middle)
+  let found_middle = dq.binary_search_by(fn(x) { x.compare(5) })
+  inspect(found_middle, content="Ok(2)")
+
+  // Find the last element that exists
+  let found_last = dq.binary_search_by(fn(x) { x.compare(9) })
+  inspect(found_last, content="Ok(4)")
+
+  // Find non-existent elements (less than all)
+  let not_found_less = dq.binary_search_by(fn(x) { x.compare(0) })
+  inspect(not_found_less, content="Err(0)")
+
+  //Find the non-existent element (middle position)
+  let not_found_middle = dq.binary_search_by(fn(x) { x.compare(4) })
+  inspect(not_found_middle, content="Err(2)")
+
+  // Find non-existent elements (greater than all)
+  let not_found_greater = dq.binary_search_by(fn(x) { x.compare(10) })
+  inspect(not_found_greater, content="Err(5)")
+}
+
+///|
+test "binary_search when wrapped around" {
+  let dq = @deque.of([5, 7, 9])
+  dq..push_front(3)..push_front(1)
+  let found_first = dq.binary_search(1)
+  inspect(found_first, content="Ok(0)")
+  let found_middle = dq.binary_search(5)
+  inspect(found_middle, content="Ok(2)")
+  let found_last = dq.binary_search(9)
+  inspect(found_last, content="Ok(4)")
+}
+
+///|
+test "binary_search on wrapped deque with first/mid/last checks" {
+  let dq = @deque.new(capacity=10)
+  for i in 1..=9 {
+    dq.push_back(i)
+  }
+  for _ in 1..=5 {
+    dq.unsafe_pop_front()
+  }
+  for i in 10..=12 {
+    dq.push_back(i)
+  }
+  inspect(dq.as_views(), content="([6, 7, 8, 9, 10], [11, 12])")
+  let found = dq.binary_search(9)
+  inspect(found, content="Ok(3)")
+  let edge_case = dq.binary_search(6)
+  inspect(edge_case, content="Ok(0)")
+  let edge_case2 = dq.binary_search(12)
+  inspect(edge_case2, content="Ok(6)")
+}
+
+///|
+test "binary_search with minimal wrap around" {
+  let dq = @deque.new(capacity=2)
+  dq..push_back(1)..push_back(2)
+  dq..unsafe_pop_front()
+  dq..push_back(3)
+  let found = dq.binary_search(2)
+  inspect(found, content="Ok(0)")
+  let not_found = dq.binary_search(1)
+  inspect(not_found, content="Err(0)")
+}
+
+///|
+test "binary_search with edge wrap around" {
+  let dq = @deque.new(capacity=4)
+  dq..push_back(1)..push_back(3)..push_back(5)..push_back(7)
+  dq..unsafe_pop_front()..unsafe_pop_front()
+  dq..push_back(9)..push_back(11)
+  inspect(dq.as_views(), content="([5, 7], [9, 11])") // Verify wrapped state
+  let found = dq.binary_search(7) // Find existing element
+  inspect(found, content="Ok(1)")
+  let not_found = dq.binary_search(8) // Find insertion point
+  inspect(not_found, content="Err(2)")
+}
+
+///|
+/// Test binary search with wrap-around buffer
+test "deque_binary_search_wrap_around" {
+  let dq = @deque.new(capacity=4)
+  dq..push_back(1)..push_back(3)..push_back(5)..push_back(7)
+  dq..unsafe_pop_front()..unsafe_pop_front()
+  dq..push_back(9)..push_back(11)
+  inspect(dq.as_views(), content="([5, 7], [9, 11])")
+  // 4. Verify binary search functionality
+  inspect(dq.binary_search(7), content="Ok(1)")
+  inspect(dq.binary_search(8), content="Err(2)")
+
+  // 5. Verify logical order
+  inspect(dq[0], content="5")
+  inspect(dq[1], content="7")
+  inspect(dq[2], content="9")
+  inspect(dq[3], content="11")
+}