rust_algorithms/searching/

binary.rs

//! Binary search (ikkilik qidiruv) va uning oilasi.
//!
//! Binary search — DSA dagi eng ko'p ishlatiladigan, eng ko'p xato qilinadigan algoritm.
//! Shu sababli bu yerda uchta muhim variant bor:
//! aniq qiymat ([`binary_search`]), chegaralar ([`lower_bound`] / [`upper_bound`])
//! va "javob ustidan qidiruv" ([`binary_search_answer`]).

use std::cmp::Ordering;

/// Tartiblangan slicedan `target` ni topadi va indeksini qaytaradi.
///
/// **G'oya:** o'rtaga qaraymiz. Katta bo'lsa — chap yarmiga, kichik bo'lsa — o'ng yarmiga
/// o'tamiz. Har qadamda qidiruv maydoni **2 baravar** qisqaradi.
///
/// - **Shart:** slice o'sish tartibida tartiblangan bo'lishi kerak.
/// - **Time:** O(log n), **Space:** O(1).
///
/// # Xavfsizlik haqida eslatma
///
/// Klassik `mid = (left + right) / 2` yozuvi `usize` da **overflow** yoki
/// `right = mid - 1` da **underflow** (panic) beradi. Shuning uchun bu yerda
/// yarim ochiq oraliq `[lo, hi)` ishlatilgan — u hech qachon manfiy bo'lmaydi.
///
/// # Misol
/// ```
/// use rust_algorithms::searching::binary_search;
///
/// let v = [1, 3, 5, 7, 9, 11];
/// assert_eq!(binary_search(&v, &7), Some(3));
/// assert_eq!(binary_search(&v, &8), None);
/// ```
pub fn binary_search<T: Ord>(list: &[T], target: &T) -> Option<usize> {
    let mut lo = 0usize;
    let mut hi = list.len(); // yarim ochiq oraliq: [lo, hi)

    while lo < hi {
        let mid = lo + (hi - lo) / 2; // overflowdan himoya
        match list[mid].cmp(target) {
            Ordering::Equal => return Some(mid),
            Ordering::Less => lo = mid + 1,
            Ordering::Greater => hi = mid,
        }
    }
    None
}

/// Binary search ning rekursiv ko'rinishi — o'quv maqsadida.
///
/// Amalda iterativ variant afzal: rekursiya stack joy egallaydi (O(log n)).
///
/// # Misol
/// ```
/// use rust_algorithms::searching::binary_search_recursive;
///
/// let v = [2, 4, 6, 8];
/// assert_eq!(binary_search_recursive(&v, &2), Some(0));
/// assert_eq!(binary_search_recursive(&v, &5), None);
/// ```
pub fn binary_search_recursive<T: Ord>(list: &[T], target: &T) -> Option<usize> {
    fn go<T: Ord>(list: &[T], target: &T, lo: usize, hi: usize) -> Option<usize> {
        if lo >= hi {
            return None;
        }
        let mid = lo + (hi - lo) / 2;
        match list[mid].cmp(target) {
            Ordering::Equal => Some(mid),
            Ordering::Less => go(list, target, mid + 1, hi),
            Ordering::Greater => go(list, target, lo, mid),
        }
    }
    go(list, target, 0, list.len())
}

/// **Birinchi** `>= target` elementning indeksi (C++ dagi `lower_bound`).
///
/// Agar bunday element bo'lmasa, `list.len()` qaytadi — ya'ni "oxiriga qo'shish kerak".
/// Bu funksiya yordamida takrorlanuvchi qiymatlarning **eng chap** o'rnini topish mumkin.
///
/// - **Time:** O(log n), **Space:** O(1).
///
/// # Misol
/// ```
/// use rust_algorithms::searching::lower_bound;
///
/// let v = [1, 2, 2, 2, 5];
/// assert_eq!(lower_bound(&v, &2), 1); // birinchi 2
/// assert_eq!(lower_bound(&v, &3), 4); // 3 yo'q → 5 turgan joy
/// assert_eq!(lower_bound(&v, &9), 5); // hammasidan katta
/// ```
pub fn lower_bound<T: Ord>(list: &[T], target: &T) -> usize {
    let mut lo = 0usize;
    let mut hi = list.len();
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if list[mid] < *target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    lo
}

/// **Birinchi** `> target` elementning indeksi (C++ dagi `upper_bound`).
///
/// `upper_bound - lower_bound` = `target` necha marta uchraganini beradi (O(log n) da!).
///
/// # Misol
/// ```
/// use rust_algorithms::searching::{lower_bound, upper_bound};
///
/// let v = [1, 2, 2, 2, 5];
/// assert_eq!(upper_bound(&v, &2), 4);
/// let nechta = upper_bound(&v, &2) - lower_bound(&v, &2);
/// assert_eq!(nechta, 3);
/// ```
pub fn upper_bound<T: Ord>(list: &[T], target: &T) -> usize {
    let mut lo = 0usize;
    let mut hi = list.len();
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if list[mid] <= *target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    lo
}

/// **Javob ustidan binary search** — olimpiada va real hayotdagi eng kuchli usul.
///
/// `lo..=hi` oralig'ida `pred` monoton (`false false ... false true true ... true`)
/// bo'lsa, `pred(x) == true` bo'lgan **eng kichik** `x` ni qaytaradi.
/// Agar hech biri `true` bo'lmasa — `None`.
///
/// **Qachon kerak:** "eng kichik sig'im", "eng qisqa vaqt", "minimal tezlik" tipidagi
/// masalalarda. Massiv emas, **javoblar oralig'i** bo'ylab qidiramiz.
///
/// - **Time:** O(log(hi-lo) × pred narxi), **Space:** O(1).
///
/// # Misol: √x ning butun qismi
/// ```
/// use rust_algorithms::searching::binary_search_answer;
///
/// let x = 1_000_000i64;
/// // "s*s >= x" birinchi marta rost bo'ladigan s ni topamiz
/// let s = binary_search_answer(0, x, |s| s * s >= x).unwrap();
/// assert_eq!(s, 1000);
/// ```
pub fn binary_search_answer<F: Fn(i64) -> bool>(lo: i64, hi: i64, pred: F) -> Option<i64> {
    let (mut lo, mut hi) = (lo, hi);
    if lo > hi {
        return None;
    }
    if !pred(hi) {
        return None; // hech qayerda rost emas
    }
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if pred(mid) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    Some(lo)
}

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

    #[test]
    fn hamma_elementni_topadi() {
        let v: Vec<i32> = (0..100).map(|x| x * 3).collect();
        for (i, x) in v.iter().enumerate() {
            assert_eq!(binary_search(&v, x), Some(i));
            assert_eq!(binary_search_recursive(&v, x), Some(i));
        }
    }

    #[test]
    fn yoq_elementga_none() {
        let v = [1, 3, 5, 7];
        for x in [0, 2, 4, 6, 8] {
            assert_eq!(binary_search(&v, &x), None, "x = {x}");
        }
    }

    #[test]
    fn bosh_va_bitta_elementli() {
        let bosh: [i32; 0] = [];
        assert_eq!(binary_search(&bosh, &1), None);
        assert_eq!(binary_search(&[42], &42), Some(0));
        assert_eq!(binary_search(&[42], &7), None);
    }

    #[test]
    fn chegaralar_takrorlanuvchi_qiymatlarda() {
        let v = [1, 2, 2, 2, 2, 9];
        assert_eq!(lower_bound(&v, &2), 1);
        assert_eq!(upper_bound(&v, &2), 5);
        assert_eq!(upper_bound(&v, &0), 0);
        assert_eq!(lower_bound(&v, &100), v.len());
    }

    #[test]
    fn javob_ustidan_qidiruv() {
        assert_eq!(binary_search_answer(0, 100, |x| x >= 37), Some(37));
        assert_eq!(binary_search_answer(0, 10, |x| x > 100), None);
        assert_eq!(binary_search_answer(0, 10_000, |s| s * s >= 144), Some(12));
    }

    #[test]
    fn std_bilan_solishtirish() {
        let v: Vec<i32> = (0..1000).step_by(7).collect();
        for x in 0..1000 {
            let ours = binary_search(&v, &x);
            let theirs = v.binary_search(&x).ok();
            assert_eq!(ours, theirs, "x = {x}");
        }
    }
}