二分搜索

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)

1. use std::cmp::Ordering;

3. pub fn binary_search<T: Ord>(item: &T, arr: &[T]) -> Option<usize> {
4. let mut left = 0;
5. let mut right = arr.len();

7. while left < right {
8. let mid = left + (right - left) / 2;

10. match item.cmp(&arr[mid]) {
11. Ordering::Less => right = mid,
12. Ordering::Equal => return Some(mid),
13. Ordering::Greater => left = mid + 1,
14. }
15. }
16. None
17. }

19. #[cfg(test)]
20. mod tests {
21. use super::*;

23. #[test]
24. fn empty() {
25. let index = binary_search(&"a", &vec![]);
26. assert_eq!(index, None);
27. }

29. #[test]
30. fn one_item() {
31. let index = binary_search(&"a", &vec!["a"]);
32. assert_eq!(index, Some(0));
33. }

35. #[test]
36. fn search_strings() {
37. let index = binary_search(&"a", &vec!["a", "b", "c", "d", "google", "zoo"]);
38. assert_eq!(index, Some(0));
39. }

41. #[test]
42. fn search_ints() {
43. let index = binary_search(&4, &vec![1, 2, 3, 4]);
44. assert_eq!(index, Some(3));

46. let index = binary_search(&3, &vec![1, 2, 3, 4]);
47. assert_eq!(index, Some(2));

49. let index = binary_search(&2, &vec![1, 2, 3, 4]);
50. assert_eq!(index, Some(1));

52. let index = binary_search(&1, &vec![1, 2, 3, 4]);
53. assert_eq!(index, Some(0));
54. }

56. #[test]
57. fn not_found() {
58. let index = binary_search(&5, &vec![1, 2, 3, 4]);
59. assert_eq!(index, None);
60. }
61. }