递归二分查找

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. }