rust_algorithms/searching/
linear.rs

1//! Linear (ketma-ket) qidiruv.
2
3/// Slice bo'ylab boshidan oxirigacha yurib, `target` ning **birinchi** indeksini qaytaradi.
4///
5/// **G'oya:** har bir elementni navbat bilan solishtiramiz. Hech qanday shart yo'q —
6/// ma'lumot tartiblanmagan bo'lsa ham ishlaydi.
7///
8/// - **Time:** O(n) — eng yomon holatda hamma elementga qaraymiz.
9/// - **Space:** O(1).
10///
11/// # Misol
12/// ```
13/// use rust_algorithms::searching::linear_search;
14///
15/// let ismlar = ["Ali", "Vali", "Hasan"];
16/// assert_eq!(linear_search(&ismlar, &"Vali"), Some(1));
17/// assert_eq!(linear_search(&ismlar, &"Olim"), None);
18/// ```
19pub fn linear_search<T: PartialEq>(list: &[T], target: &T) -> Option<usize> {
20    for (index, item) in list.iter().enumerate() {
21        if item == target {
22            return Some(index);
23        }
24    }
25    None
26}
27
28/// Shart (predikat) bo'yicha qidiradi: shartni qanoatlantirgan birinchi indeks.
29///
30/// `linear_search` ning umumlashgan ko'rinishi — "teng bo'lgan" emas,
31/// "menga mos keladigan" elementni topadi.
32///
33/// - **Time:** O(n), **Space:** O(1).
34///
35/// # Misol
36/// ```
37/// use rust_algorithms::searching::linear_search_by;
38///
39/// let sonlar = [3, 7, 8, 11];
40/// // birinchi juft son:
41/// assert_eq!(linear_search_by(&sonlar, |x| x % 2 == 0), Some(2));
42/// ```
43pub fn linear_search_by<T, F: Fn(&T) -> bool>(list: &[T], pred: F) -> Option<usize> {
44    for (index, item) in list.iter().enumerate() {
45        if pred(item) {
46            return Some(index);
47        }
48    }
49    None
50}
51
52/// `target` uchraydigan **barcha** indekslarni qaytaradi.
53///
54/// - **Time:** O(n), **Space:** O(k) — bu yerda k topilgan mosliklar soni.
55///
56/// # Misol
57/// ```
58/// use rust_algorithms::searching::linear_search_all;
59///
60/// let v = [1, 2, 1, 3, 1];
61/// assert_eq!(linear_search_all(&v, &1), vec![0, 2, 4]);
62/// ```
63pub fn linear_search_all<T: PartialEq>(list: &[T], target: &T) -> Vec<usize> {
64    list.iter()
65        .enumerate()
66        .filter(|(_, item)| *item == target)
67        .map(|(index, _)| index)
68        .collect()
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn topadi_va_topmaydi() {
77        let v = [0, 1, 2, 3, 4, 5];
78        assert_eq!(linear_search(&v, &0), Some(0));
79        assert_eq!(linear_search(&v, &5), Some(5));
80        assert_eq!(linear_search(&v, &42), None);
81    }
82
83    #[test]
84    fn bosh_slice() {
85        let v: [i32; 0] = [];
86        assert_eq!(linear_search(&v, &1), None);
87        assert_eq!(linear_search_all(&v, &1), Vec::<usize>::new());
88    }
89
90    #[test]
91    fn takrorlanuvchi_qiymatlarda_birinchisini_qaytaradi() {
92        let v = [4, 4, 4];
93        assert_eq!(linear_search(&v, &4), Some(0));
94    }
95
96    #[test]
97    fn predikat_bilan() {
98        let v = [1, 3, 5, 6, 7];
99        assert_eq!(linear_search_by(&v, |x| x % 2 == 0), Some(3));
100        assert_eq!(linear_search_by(&v, |x| *x > 100), None);
101    }
102}
rust_algorithms/searching/linear.rs

rust_algorithms/searching/
linear.rs
