rust_algorithms/searching/

advanced.rs

//! Qo'shimcha qidiruv algoritmlari: jump, interpolation, exponential, ternary.

/// Jump search — tartiblangan massivda √n qadamlab "sakrab" qidirish.
///
/// **G'oya:** har `√n` qadamda bir marta qaraymiz; `target` dan katta blok topilsa,
/// shu blok ichida linear search qilamiz.
///
/// **Nega kerak?** Disk/lentaga o'xshash, "orqaga qaytish qimmat" bo'lgan
/// muhitlarda binary searchdan ko'ra kamroq sakrash qiladi.
///
/// - **Time:** O(√n), **Space:** O(1). Shart: tartiblangan bo'lishi.
///
/// # Misol
/// ```
/// use rust_algorithms::searching::jump_search;
///
/// let v: Vec<i32> = (0..100).collect();
/// assert_eq!(jump_search(&v, &73), Some(73));
/// assert_eq!(jump_search(&v, &1000), None);
/// ```
pub fn jump_search<T: Ord>(list: &[T], target: &T) -> Option<usize> {
    let n = list.len();
    if n == 0 {
        return None;
    }
    let step = (n as f64).sqrt().ceil() as usize;
    let step = step.max(1);

    // 1) target bo'lishi mumkin bo'lgan blokni topamiz
    let mut block_start = 0usize;
    while block_start < n && list[(block_start + step - 1).min(n - 1)] < *target {
        block_start += step;
    }
    if block_start >= n {
        return None;
    }

    // 2) blok ichida linear search
    let block_end = (block_start + step).min(n);
    (block_start..block_end).find(|&i| list[i] == *target)
}

/// Interpolation search — qiymatlar **tekis taqsimlangan** bo'lsa binary searchdan tez.
///
/// **G'oya:** o'rtaga emas, qiymatga qarab "taxmin qilingan" joyga sakraymiz —
/// lug'atdan "Zokir" so'zini oxiridan qidirganingizdek.
///
/// - **Time:** o'rtacha O(log log n), eng yomon holatda O(n) (masalan, 1,2,4,8,…,2^k).
/// - **Space:** O(1). Shart: tartiblangan `i64` slice.
///
/// # Misol
/// ```
/// use rust_algorithms::searching::interpolation_search;
///
/// let v: Vec<i64> = (0..1000).map(|x| x * 2).collect();
/// assert_eq!(interpolation_search(&v, 400), Some(200));
/// assert_eq!(interpolation_search(&v, 401), None);
/// ```
pub fn interpolation_search(list: &[i64], target: i64) -> Option<usize> {
    if list.is_empty() {
        return None;
    }
    let (mut lo, mut hi) = (0usize, list.len() - 1);

    while lo <= hi && target >= list[lo] && target <= list[hi] {
        if list[hi] == list[lo] {
            return if list[lo] == target { Some(lo) } else { None };
        }
        // chiziqli interpolyatsiya: qiymat oralig'idagi nisbatni indekslarga ko'chiramiz
        let span = (list[hi] - list[lo]) as i128;
        let offset = ((target - list[lo]) as i128 * (hi - lo) as i128) / span;
        let pos = lo + offset as usize;

        match list[pos].cmp(&target) {
            std::cmp::Ordering::Equal => return Some(pos),
            std::cmp::Ordering::Less => lo = pos + 1,
            std::cmp::Ordering::Greater => {
                if pos == 0 {
                    return None;
                }
                hi = pos - 1;
            }
        }
    }
    None
}

/// Exponential search — avval oraliqni 1, 2, 4, 8… deb kengaytirib topadi,
/// so'ng shu oraliqda binary search qiladi.
///
/// **Qachon kerak:** massiv juda katta (yoki uzunligi noma'lum) va qidirilayotgan
/// element **boshiga yaqin** bo'lsa. `i` — javob indeksi bo'lsa, narxi O(log i).
///
/// - **Time:** O(log i), **Space:** O(1). Shart: tartiblangan.
///
/// # Misol
/// ```
/// use rust_algorithms::searching::exponential_search;
///
/// let v: Vec<i32> = (0..1_000_000).collect();
/// assert_eq!(exponential_search(&v, &5), Some(5)); // deyarli bir zumda
/// ```
pub fn exponential_search<T: Ord>(list: &[T], target: &T) -> Option<usize> {
    let n = list.len();
    if n == 0 {
        return None;
    }
    if list[0] == *target {
        return Some(0);
    }

    let mut bound = 1usize;
    while bound < n && list[bound] < *target {
        bound *= 2;
    }
    let lo = bound / 2;
    let hi = (bound + 1).min(n);

    // [lo, hi) oralig'ida binary search
    super::binary_search(&list[lo..hi], target).map(|i| i + lo)
}

/// Ternary search — **unimodal** (avval o'sib, keyin kamayadigan) funksiya maksimumi.
///
/// **G'oya:** oraliqni har qadamda uchga bo'lib, maksimum bo'lishi mumkin bo'lmagan
/// uchdan birini tashlab yuboramiz.
///
/// `eps` — kerakli aniqlik. Qaytadi: maksimum bo'lgan `x`.
///
/// - **Time:** O(log((hi-lo)/eps)), **Space:** O(1).
///
/// # Misol
/// ```
/// use rust_algorithms::searching::ternary_search_max;
///
/// // f(x) = -(x-3)^2 + 10 → maksimum x = 3 da
/// let x = ternary_search_max(-10.0, 10.0, 1e-9, |x| -(x - 3.0) * (x - 3.0) + 10.0);
/// assert!((x - 3.0).abs() < 1e-5);
/// ```
pub fn ternary_search_max<F: Fn(f64) -> f64>(lo: f64, hi: f64, eps: f64, f: F) -> f64 {
    let (mut lo, mut hi) = (lo, hi);
    while hi - lo > eps {
        let m1 = lo + (hi - lo) / 3.0;
        let m2 = hi - (hi - lo) / 3.0;
        if f(m1) < f(m2) {
            lo = m1;
        } else {
            hi = m2;
        }
    }
    (lo + hi) / 2.0
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn jump_hamma_elementni_topadi() {
        let v: Vec<i32> = (0..200).map(|x| x * 5).collect();
        for (i, x) in v.iter().enumerate() {
            assert_eq!(jump_search(&v, x), Some(i), "x = {x}");
        }
        assert_eq!(jump_search(&v, &3), None);
        assert_eq!(jump_search::<i32>(&[], &1), None);
    }

    #[test]
    fn interpolation_hamma_elementni_topadi() {
        let v: Vec<i64> = (0..500).map(|x| x * 3 + 7).collect();
        for (i, &x) in v.iter().enumerate() {
            assert_eq!(interpolation_search(&v, x), Some(i), "x = {x}");
        }
        assert_eq!(interpolation_search(&v, 8), None);
        assert_eq!(interpolation_search(&[], 1), None);
        assert_eq!(interpolation_search(&[5, 5, 5], 5), Some(0));
        assert_eq!(interpolation_search(&[5, 5, 5], 4), None);
    }

    #[test]
    fn exponential_hamma_elementni_topadi() {
        let v: Vec<i32> = (0..1000).map(|x| x * 2).collect();
        for (i, x) in v.iter().enumerate() {
            assert_eq!(exponential_search(&v, x), Some(i), "x = {x}");
        }
        assert_eq!(exponential_search(&v, &1), None);
        assert_eq!(exponential_search(&v, &10_000), None);
        assert_eq!(exponential_search::<i32>(&[], &0), None);
    }

    #[test]
    fn ternary_maksimumni_topadi() {
        let x = ternary_search_max(0.0, 100.0, 1e-9, |x| -(x - 42.0).powi(2));
        assert!((x - 42.0).abs() < 1e-4);
    }
}