An Overview of Rust Search Algorithms
Search algorithms and their implementation in Rust, a systems programming language designed for safety, concurrency, and performance.
Various search algorithms, from basic linear search to advanced artificial intelligence-based techniques, are discussed in this article.
You can expect to learn the following as we progress through this guide:
Rust’s unique feature
Detailed explanations and code examples
Performance analysis and optimization techniques
This article will equip you with a solid understanding of search algorithms and their Rust implementations, so you can tackle complex problems with ease and confidence. A comprehensive guide to search algorithms is the perfect resource for anyone looking to expand their Rust skills or to learn more about search algorithms.
use std::cmp::Ordering;
pub fn binary_search<T: Ord>(item: &T, arr: &[T]) -> Option<usize> {
let mut is_asc = true;
if arr.len() > 1 {
is_asc = arr[0] < arr[arr.len() - 1];
}
let mut left = 0;
let mut right = arr.len();
while left < right {
let mid = left + (right - left) / 2;
if is_asc {
match item.cmp(&arr[mid]) {
Ordering::Less => right = mid,
Ordering::Equal => return Some(mid),
Ordering::Greater => left = mid + 1,
}
} else {
match item.cmp(&arr[mid]) {
Ordering::Less => left = mid + 1,
Ordering::Equal => return Some(mid),
Ordering::Greater => right = mid,
}
}
}
None
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn empty() {
let index = binary_search(&"a", &[]);
assert_eq!(index, None);
}
#[test]
fn one_item() {
let index = binary_search(&"a", &["a"]);
assert_eq!(index, Some(0));
}
#[test]
fn search_strings_asc() {
let index = binary_search(&"a", &["a", "b", "c", "d", "google", "zoo"]);
assert_eq!(index, Some(0));
let index = binary_search(&"google", &["a", "b", "c", "d", "google", "zoo"]);
assert_eq!(index, Some(4));
}
#[test]
fn search_strings_desc() {
let index = binary_search(&"a", &["zoo", "google", "d", "c", "b", "a"]);
assert_eq!(index, Some(5));
let index = binary_search(&"zoo", &["zoo", "google", "d", "c", "b", "a"]);
assert_eq!(index, Some(0));
let index = binary_search(&"google", &["zoo", "google", "d", "c", "b", "a"]);
assert_eq!(index, Some(1));
}
#[test]
fn search_ints_asc() {
let index = binary_search(&4, &[1, 2, 3, 4]);
assert_eq!(index, Some(3));
let index = binary_search(&3, &[1, 2, 3, 4]);
assert_eq!(index, Some(2));
let index = binary_search(&2, &[1, 2, 3, 4]);
assert_eq!(index, Some(1));
let index = binary_search(&1, &[1, 2, 3, 4]);
assert_eq!(index, Some(0));
}
#[test]
fn search_ints_desc() {
let index = binary_search(&4, &[4, 3, 2, 1]);
assert_eq!(index, Some(0));
let index = binary_search(&3, &[4, 3, 2, 1]);
assert_eq!(index, Some(1));
let index = binary_search(&2, &[4, 3, 2, 1]);
assert_eq!(index, Some(2));
let index = binary_search(&1, &[4, 3, 2, 1]);
assert_eq!(index, Some(3));
}
#[test]
fn not_found() {
let index = binary_search(&5, &[1, 2, 3, 4]);
assert_eq!(index, None);
let index = binary_search(&5, &[4, 3, 2, 1]);
assert_eq!(index, None);
}
}
In this Rust code, a binary search algorithm is implemented for an ordered array of values. The process is as follows:
The function signature binary_search<T: Ord>(item: &T, arr: &[T]) -> Option<usize> indicates the function takes two parameters: a reference to the element being searched for and a slice of the array to search in. The function returns an Option<usize> which can either be Some(index) if the item is found at the given index, or None if it is not found.
To determine whether the array is sorted ascendingly or descendingly, the function first checks whether the array has more than one element.
The left and right variables are initialized to the array’s start and end indices.
The array is repeatedly searched using a while loop. As long as the left index is less than the right index, the loop runs.
During the loop, the function calculates the mid index by finding the midpoint between left and right.
When the array is sorted in ascending order, a match expression checks whether the item being searched for is less than, equal to, or greater than the item at the mid index. By setting right to mid, the search is restricted to the left half of the array if it is less than the mid item. In this case, the midindex is returned as a Some value if it is equal to the mid item. By setting left to mid + 1, the search is restricted to the right half of the array if it is greater than the mid item.
In descending order, the same match expression is used, but the Less and Greater cases are reversed. Searching a descending array follows the opposite logic from searching an ascending array.
Upon completion of the while loop without finding the item, the function returns None.
Several test cases are also included in the code, checking for different input arrays and items. Assert_eq! is used in the tests. Using this macro, you can verify that the output of the function matches what you expected.
Binary Search Recursive
use std::cmp::Ordering;
pub fn binary_search_rec<T: Ord>(
list_of_items: &[T],
target: &T,
left: &usize,
right: &usize,
) -> Option<usize> {
if left >= right {
return None;
}
let is_asc = list_of_items[0] < list_of_items[list_of_items.len() - 1];
let middle: usize = left + (right - left) / 2;
if is_asc {
match target.cmp(&list_of_items[middle]) {
Ordering::Less => binary_search_rec(list_of_items, target, left, &middle),
Ordering::Greater => binary_search_rec(list_of_items, target, &(middle + 1), right),
Ordering::Equal => Some(middle),
}
} else {
match target.cmp(&list_of_items[middle]) {
Ordering::Less => binary_search_rec(list_of_items, target, &(middle + 1), right),
Ordering::Greater => binary_search_rec(list_of_items, target, left, &middle),
Ordering::Equal => Some(middle),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
const LEFT: usize = 0;
#[test]
fn fail_empty_list() {
let list_of_items = vec![];
assert_eq!(
binary_search_rec(&list_of_items, &1, &LEFT, &list_of_items.len()),
None
);
}
#[test]
fn success_one_item() {
let list_of_items = vec![30];
assert_eq!(
binary_search_rec(&list_of_items, &30, &LEFT, &list_of_items.len()),
Some(0)
);
}
#[test]
fn success_search_strings_asc() {
let say_hello_list = vec!["hi", "olá", "salut"];
let right = say_hello_list.len();
assert_eq!(
binary_search_rec(&say_hello_list, &"hi", &LEFT, &right),
Some(0)
);
assert_eq!(
binary_search_rec(&say_hello_list, &"salut", &LEFT, &right),
Some(2)
);
}
#[test]
fn success_search_strings_desc() {
let say_hello_list = vec!["salut", "olá", "hi"];
let right = say_hello_list.len();
assert_eq!(
binary_search_rec(&say_hello_list, &"hi", &LEFT, &right),
Some(2)
);
assert_eq!(
binary_search_rec(&say_hello_list, &"salut", &LEFT, &right),
Some(0)
);
}
#[test]
fn fail_search_strings_asc() {
let say_hello_list = vec!["hi", "olá", "salut"];
for target in &["adiós", "你好"] {
assert_eq!(
binary_search_rec(&say_hello_list, target, &LEFT, &say_hello_list.len()),
None
);
}
}
#[test]
fn fail_search_strings_desc() {
let say_hello_list = vec!["salut", "olá", "hi"];
for target in &["adiós", "你好"] {
assert_eq!(
binary_search_rec(&say_hello_list, target, &LEFT, &say_hello_list.len()),
None
);
}
}
#[test]
fn success_search_integers_asc() {
let integers = vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90];
for (index, target) in integers.iter().enumerate() {
assert_eq!(
binary_search_rec(&integers, target, &LEFT, &integers.len()),
Some(index)
)
}
}
#[test]
fn success_search_integers_desc() {
let integers = vec![90, 80, 70, 60, 50, 40, 30, 20, 10, 0];
for (index, target) in integers.iter().enumerate() {
assert_eq!(
binary_search_rec(&integers, target, &LEFT, &integers.len()),
Some(index)
)
}
}
#[test]
fn fail_search_integers() {
let integers = vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90];
for target in &[100, 444, 336] {
assert_eq!(
binary_search_rec(&integers, target, &LEFT, &integers.len()),
None
);
}
}
#[test]
fn success_search_string_in_middle_of_unsorted_list() {
let unsorted_strings = vec!["salut", "olá", "hi"];
assert_eq!(
binary_search_rec(&unsorted_strings, &"olá", &LEFT, &unsorted_strings.len()),
Some(1)
);
}
#[test]
fn success_search_integer_in_middle_of_unsorted_list() {
let unsorted_integers = vec![90, 80, 70];
assert_eq!(
binary_search_rec(&unsorted_integers, &80, &LEFT, &unsorted_integers.len()),
Some(1)
);
}
}
To find a target item in an ordered array of items, this Rust code implements a recursive binary search algorithm. The process is as follows:
Binary_search_rec<T: Ord>(list_of_items: &[T], target: &T, left: &usize, right: &usize) -> Option<usize> indicates that the function takes four parameters: a slice of ordered items, the target item to search for, and two usize variables representing the left and right boundaries of the slice. If the item is found at the given index, the function returns Some(index), otherwise it returns None.
Initially, the function checks if the left index is greater than or equal to the right index, indicating that the slice of items has been exhausted without finding the target item. The function returns None in this case.
By checking if the first item in the slice is less than the last item, the function determines whether the slice is sorted ascending or descending.
Middle index is calculated as the midpoint between left and right.
When the slice is sorted ascendingly, a match expression checks if the target item is less than, greater than, or equal to the middle item. Recursively calling binary_search_rec with the same left index and the middle index as the new right index limits the search to the left half of the slice if it is less than the middle item. Recursively calling binary_search_rec with the middle + 1 index as the new left index and the same right index limits the search to the right half of the slice if it is greater than the middle item. A function returns Some(middle) if its value equals the middle item.
The same match expression is used if the slice is sorted descendingly, but the Less and Greater cases are reversed. The logic for searching a descending slice is opposite that for searching an ascending slice.
There are several test cases for the function, checking for various input slices and target items. Tests are run using assert_eq! The output of the function should match what is expected.