二分搜索
From Wikipedia: Binary search, also known as half-interval search or logarithmic search, is a search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful.
Properties
- Worst case performance O(log n)
- Best case performance O(1)
- Average case performance O(log n)
- Worst case space complexity O(1)
use std::cmp::Ordering;
pub fn binary_search<T: Ord>(item: &T, arr: &[T]) -> Option<usize> {
let mut left = 0;
let mut right = arr.len();
while left < right {
let mid = left + (right - left) / 2;
match item.cmp(&arr[mid]) {
Ordering::Less => right = mid,
Ordering::Equal => return Some(mid),
Ordering::Greater => left = mid + 1,
}
}
None
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn empty() {
let index = binary_search(&"a", &vec![]);
assert_eq!(index, None);
}
#[test]
fn one_item() {
let index = binary_search(&"a", &vec!["a"]);
assert_eq!(index, Some(0));
}
#[test]
fn search_strings() {
let index = binary_search(&"a", &vec!["a", "b", "c", "d", "google", "zoo"]);
assert_eq!(index, Some(0));
}
#[test]
fn search_ints() {
let index = binary_search(&4, &vec![1, 2, 3, 4]);
assert_eq!(index, Some(3));
let index = binary_search(&3, &vec![1, 2, 3, 4]);
assert_eq!(index, Some(2));
let index = binary_search(&2, &vec![1, 2, 3, 4]);
assert_eq!(index, Some(1));
let index = binary_search(&1, &vec![1, 2, 3, 4]);
assert_eq!(index, Some(0));
}
#[test]
fn not_found() {
let index = binary_search(&5, &vec![1, 2, 3, 4]);
assert_eq!(index, None);
}
}
当前内容版权归 rustlang-cn 或其关联方所有,如需对内容或内容相关联开源项目进行关注与资助,请访问 rustlang-cn .