递归二分查找

  1. use std::cmp::Ordering;
  3. pub fn binary_search_rec<T: Ord>(
  4.     list_of_items: &[T],
  5.     target: &T,
  6.     left: &usize,
  7.     right: &usize,
  8. ) -> Option<usize> {
  9.     if left >= right {
  10.         return None;
  11.     }
  13.     let middle: usize = left + (right - left) / 2;
  14.     match target.cmp(&list_of_items[middle]) {
  15.         Ordering::Less => binary_search_rec(list_of_items, target, left, &middle),
  16.         Ordering::Greater => binary_search_rec(list_of_items, target, &(middle + 1), right),
  17.         Ordering::Equal => Some(middle),
  18.     }
  19. }
  21. #[cfg(test)]
  22. mod tests {
  23.     use super::*;
  25.     const LEFT: usize = 0;
  27.     #[test]
  28.     fn fail_empty_list() {
  29.         let list_of_items = vec![];
  30.         assert_eq!(
  31.             binary_search_rec(&list_of_items, &1, &LEFT, &list_of_items.len()),
  32.             None
  33.         );
  34.     }
  36.     #[test]
  37.     fn success_one_item() {
  38.         let list_of_items = vec![30];
  39.         assert_eq!(
  40.             binary_search_rec(&list_of_items, &30, &LEFT, &list_of_items.len()),
  41.             Some(0)
  42.         );
  43.     }
  45.     #[test]
  46.     fn success_search_strings() {
  47.         let say_hello_list = vec!["hi", "olá", "salut"];
  48.         let right = say_hello_list.len();
  49.         assert_eq!(
  50.             binary_search_rec(&say_hello_list, &"hi", &LEFT, &right),
  51.             Some(0)
  52.         );
  53.         assert_eq!(
  54.             binary_search_rec(&say_hello_list, &"salut", &LEFT, &right),
  55.             Some(2)
  56.         );
  57.     }
  59.     #[test]
  60.     fn fail_search_strings() {
  61.         let say_hello_list = vec!["hi", "olá", "salut"];
  62.         for target in &["adiós", "你好"] {
  63.             assert_eq!(
  64.                 binary_search_rec(&say_hello_list, target, &LEFT, &say_hello_list.len()),
  65.                 None
  66.             );
  67.         }
  68.     }
  70.     #[test]
  71.     fn success_search_integers() {
  72.         let integers = vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90];
  73.         for (index, target) in integers.iter().enumerate() {
  74.             assert_eq!(
  75.                 binary_search_rec(&integers, target, &LEFT, &integers.len()),
  76.                 Some(index)
  77.             )
  78.         }
  79.     }
  81.     #[test]
  82.     fn fail_search_integers() {
  83.         let integers = vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90];
  84.         for target in &[100, 444, 336] {
  85.             assert_eq!(
  86.                 binary_search_rec(&integers, target, &LEFT, &integers.len()),
  87.                 None
  88.             );
  89.         }
  90.     }
  92.     #[test]
  93.     fn fail_search_unsorted_strings_list() {
  94.         let unsorted_strings = vec!["salut", "olá", "hi"];
  95.         for target in &["hi", "salut"] {
  96.             assert_eq!(
  97.                 binary_search_rec(&unsorted_strings, target, &LEFT, &unsorted_strings.len()),
  98.                 None
  99.             );
  100.         }
  101.     }
  103.     #[test]
  104.     fn fail_search_unsorted_integers_list() {
  105.         let unsorted_integers = vec![90, 80, 70, 60, 50, 40, 30, 20, 10, 0];
  106.         for target in &[0, 80, 90] {
  107.             assert_eq!(
  108.                 binary_search_rec(&unsorted_integers, target, &LEFT, &unsorted_integers.len()),
  109.                 None
  110.             );
  111.         }
  112.     }
  114.     #[test]
  115.     fn success_search_string_in_middle_of_unsorted_list() {
  116.         let unsorted_strings = vec!["salut", "olá", "hi"];
  117.         assert_eq!(
  118.             binary_search_rec(&unsorted_strings, &"olá", &LEFT, &unsorted_strings.len()),
  119.             Some(1)
  120.         );
  121.     }
  123.     #[test]
  124.     fn success_search_integer_in_middle_of_unsorted_list() {
  125.         let unsorted_integers = vec![90, 80, 70];
  126.         assert_eq!(
  127.             binary_search_rec(&unsorted_integers, &80, &LEFT, &unsorted_integers.len()),
  128.             Some(1)
  129.         );
  130.     }
  131. }