dsa_rust/algorithms/
list_processing.rs

1pub mod recursion {
2    pub fn recursion(n: i32) {
3        // Defines base case
4        if n >= 10 {
5            // Recursive call to self
6            recursion(n / 10);
7        }
8        // Prints the digit
9        println!("{}", n % 10)
10    }
11}
12
13pub mod binary_search {
14    /** My (iterative) version of a binary search implementation;
15     * Takes a sorted array and a key and returns either Some(index) or None */
16    pub fn binary_search(a: &[i32], key: i32) -> Option<i32> {
17        use std::cmp::Ordering;
18    
19        // Sets initial position of the search boundaries
20        let mut left = 0;
21        let mut right = a.len() - 1;
22    
23        // Loops until the search boundaries overlap;
24        // If the loop doesn't find the key, the function
25        // returns None
26        while left <= right {
27            let mid = (left + right) / 2;
28            match a[mid].cmp(&key) {
29                Ordering::Equal => return Some(mid as i32),
30                Ordering::Greater => right = mid - 1,
31                Ordering::Less => left = mid + 1,
32            }
33            //if a[mid] == key {
34            //    return Some(mid as i32);
35            //} else if a[mid] > key {
36            //    right = mid - 1;
37            //} else {
38            //    left = mid + 1;
39            //}
40            //match key {
41            //    val if val == a[mid] => Some(mid as i32),
42            //    _ => Some(0)
43            //};
44            println!("Guess index: {}", &mid);
45        }
46        None
47    }
48    
49    #[test]
50    pub fn binary_search_test() {
51        // The target 73 exists at the 37th index
52        let target = 73;
53        let array: [i32; 39] = [
54            1, 4, 5, 6, 10, 12, 16, 21, 23, 24, 25, 27, 31, 32, 33, 35, 37, 39, 40, 41, 42, 43, 45, 47,
55            49, 50, 51, 52, 54, 56, 57, 60, 61, 67, 70, 71, 72, 73, 74,
56        ];
57        let result = binary_search(&array, target).unwrap_or_default();
58        assert_eq!(result, 37)
59    }
60}
61
62pub mod substring_search {
63    use std::collections::HashMap;
64    
65    fn longest_unique_substring(s: &str) -> usize {
66        let mut map = HashMap::new(); // As HashMap<char, i32>
67        let mut left = 0;
68        let mut max_len = 0;
69    
70        let chars: Vec<char> = s.chars().collect();
71    
72        for right in 0..chars.len() {
73            *map.entry(chars[right]).or_insert(0) += 1;
74    
75            while map[&chars[right]] > 1 {
76                *map.get_mut(&chars[left]).unwrap() -= 1;
77                left += 1;
78            }
79    
80            max_len = max_len.max(right - left + 1);
81        }
82    
83        max_len
84    }
85    
86    fn longest_unique_substring_print(s: &str) -> usize {
87        let mut map = HashMap::new();
88        let mut left = 0;
89        let mut max_len = 0;
90        let mut best_range = (0, 0); // To store (start, end)
91    
92        let chars: Vec<char> = s.chars().collect();
93    
94        for right in 0..chars.len() {
95            *map.entry(chars[right]).or_insert(0) += 1;
96    
97            while map[&chars[right]] > 1 {
98                *map.get_mut(&chars[left]).unwrap() -= 1;
99                left += 1;
100            }
101    
102            let current_len = right - left + 1;
103            if current_len > max_len {
104                max_len = current_len;
105                best_range = (left, right);
106            }
107        }
108    
109        // Print the substring using the captured indices
110        let result: String = chars[best_range.0..=best_range.1].iter().collect();
111        println!("Longest substring found: \"{result}\" (length {max_len})");
112    
113        max_len
114    }
115    
116    #[test]
117    fn longest_unique_substring_test() {
118        let s = "this is a llama test.";
119        assert_eq!(longest_unique_substring(s), 6);
120        longest_unique_substring_print(s);
121        //panic!()
122    }
123}
dsa_rust/algorithms/list_processing.rs

dsa_rust/algorithms/
list_processing.rs
