dsa_rust/maw/
maw_01.rs

1/*!
2This is a sandbox crate for chapter 1 of Data Structures and Algorithm Analysis in Java by Mark Allen Weiss
3*/
4
5pub fn recursion(n: i32) {
6    // Defines base case
7    if n >= 10 {
8        // Recursive call to self
9        recursion(n / 10);
10    }
11    // Prints the digit
12    println!("{}", n % 10)
13}
14
15/** My (iterative) version of a binary search implementation;
16 * Takes a sorted array and a key and returns either Some(index) or None */
17pub fn binary_search(a: &[i32], key: i32) -> Option<i32> {
18    use std::cmp::Ordering;
19
20    // Sets initial position of the search boundaries
21    let mut left = 0;
22    let mut right = a.len() - 1;
23
24    // Loops until the search boundaries overlap;
25    // If the loop doesn't find the key, the function
26    // returns None
27    while left <= right {
28        let mid = (left + right) / 2;
29        match a[mid].cmp(&key) {
30            Ordering::Equal => return Some(mid as i32),
31            Ordering::Greater => right = mid - 1,
32            Ordering::Less => left = mid + 1,
33        }
34        //if a[mid] == key {
35        //    return Some(mid as i32);
36        //} else if a[mid] > key {
37        //    right = mid - 1;
38        //} else {
39        //    left = mid + 1;
40        //}
41        //match key {
42        //    val if val == a[mid] => Some(mid as i32),
43        //    _ => Some(0)
44        //};
45        println!("Guess index: {}", &mid);
46    }
47    None
48}
49
50#[test]
51pub fn binary_search_test() {
52    // The target 73 exists at the 37th index
53    let target = 73;
54    let array: [i32; 39] = [
55        1, 4, 5, 6, 10, 12, 16, 21, 23, 24, 25, 27, 31, 32, 33, 35, 37, 39, 40, 41, 42, 43, 45, 47,
56        49, 50, 51, 52, 54, 56, 57, 60, 61, 67, 70, 71, 72, 73, 74,
57    ];
58    let result = binary_search(&array, target).unwrap_or_default();
59    assert_eq!(result, 37)
60}
dsa_rust/maw/maw_01.rs

dsa_rust/maw/
maw_01.rs
