Table of content

Binary Search in Rust

Binary search, also known as logarithmic search, is a search algorithm that quickly finds out specific elements in a sequence that have been sorted. The step of binary search is like playing guess numbers.

First, guess a number, telling you that your guess is bigger or smaller than the correct answer, then continue to guess in the right direction and discard the other half of the guess. This continues to make several guesses. Each time you guess, the search range is reduced by half, so it is called a "binary" search.

Binary search has the following characteristics:

The concept is simple, the search is efficient, and the log execution time is $O(log n)$.
No additional material structure or configuration memory space is required.
Only sorted sequences can be searched.

step
  • Start with the elements in the middle of the sequence and compare them to the target value
  • If the element is a search target, the search ends.
  • If the element is larger or smaller, cut the sequence in half and search for the smaller or larger half.
  • Continue with the elements in the middle of half of the sequence and repeat steps one through three until the sequence to be searched is empty.
Description'

There is an ordered sequence of 15 elements, and now you are looking for 9 in the sequence.

[2, 3, 3, 6, 6, 7, 9, 13, 15, 19, 20, 22, 23, 24, 25]
First, find the middle element 15 / 2 ~ = 8, the eighth element is 13, which is larger than 9, so discard all elements after the eighth element.

[2, 3, 3, 6, 6, 7, 9, _, _, _, _, _, _, _, _]
Next, continue to search for half search, 8 / 2 = 4, find the fourth element to compare, 6 to 9 small, so discard all elements before the fourth element.

[_, _, _, 6, 6, 7, 9, _, _, _, _, _, _, _, _]
Binary search for the remaining elements, 4 / 2 = 2, and calculate the midpoint from the fourth element 4 + 2 = 6, get the sixth element to be 7, smaller than 9, and discard the elements before 7.

[_, _, _, _, _, 7, 9, _, _, _, _, _, _, _, _]
Continue to cut in half to search, continue to find the middle element 2 / 2 = 1, and calculate the index position from the sixth element 6 + 1 = 7, view the seventh element is 9, finally found!

/// Handmade binary search for a sorted sequence.

/// This version of binary search does not guarantee retrieval of the leftmost

/// matching position if multiple elements found.

/// Reference:

/// - [`std::slice::binary_search`][1]

pub fn binary_search<T>(arr: &[T], target: &T) -> Result<usize, usize>
where T: PartialOrd,
{ let mut size = arr.len(); if size == 0 { return Err(0); } let mut base = 0_usize;

while size > 1 { // mid: [base..size) let half = size / 2; let mid = base + half; if arr[mid] <= *target { base = mid } size -= half; }

if arr[base] == *target { Ok(base) } else { // Return the expected position in the array. Err(base + (arr[base] < *target) as usize) } }

#[cfg(test)]
mod base { use super::*;

sorted_no_duplicate_cases!(binary_search); }

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions