Vec::binary_search în Rust

pub fn binary_search(&self, x: &T) -> Result<usize, usize>   // T: Ord

Ce face Vec::binary_search

Căutarea binară împarte vectorul în jumătăți la fiecare pas, deci găsește un element dintr-un milion în cel mult 20 de comparații. Condiția este ca vectorul să fie sortat crescător; pe un vector nesortat, rezultatul nu are sens.

Rezultatul este un Result: Ok(i) dacă valoarea există pe poziția i (dacă apare de mai multe ori, oricare dintre poziții poate fi returnată) și Err(i) dacă nu există, unde i este poziția la care ar trebui inserată ca vectorul să rămână sortat.

Variantele binary_search_by_key(&cheie, |e| ...) și binary_search_by(|e| ...) caută după un câmp sau după o comparație proprie, de exemplu într-un vector de structuri sortat după nume.

Parametri

Parametru	Descriere
x	Referință la valoarea căutată.

Ce returnează

Ok(poziție) dacă valoarea există, altfel Err(poziția de inserare).

Exemple

Exemplul 1: Ani importanți

fn main() {
    let ani = vec![1859, 1918, 1989, 2004, 2007];
    println!("{:?}", ani.binary_search(&1918));
    println!("{:?}", ani.binary_search(&2000));
    match ani.binary_search(&2026) {
        Ok(i) => println!("găsit la {i}"),
        Err(i) => println!("2026 nu există; s-ar insera pe poziția {i}"),
    }
}

Rezultat

Ok(1)
Err(3)
2026 nu există; s-ar insera pe poziția 5

Exemplul 2: Căutare după nume într-o listă de prețuri

Lista este sortată după nume, deci căutăm cu binary_search_by_key, cu numele drept cheie.

fn main() {
    let preturi = vec![("cafea", 25), ("lapte", 8), ("pâine", 5), ("unt", 12)];
    for cautat in ["pâine", "miere"] {
        match preturi.binary_search_by_key(&cautat, |&(nume, _)| nume) {
            Ok(i) => println!("{cautat}: {} lei", preturi[i].1),
            Err(_) => println!("{cautat}: nu avem"),
        }
    }
}

Rezultat

pâine: 5 lei
miere: nu avem

Exemplul 3: Pe un vector nesortat, rezultatul e greșit

Și 10, și 50 există în vector, dar căutarea binară răspunde Err, pentru că vectorul nu este sortat. După sort, răspunsurile sunt corecte.

fn main() {
    let mut v = vec![20, 50, 40, 10, 30];
    println!("nesortat {:?}: 10 -> {:?}, 50 -> {:?}", v, v.binary_search(&10), v.binary_search(&50));
    v.sort();
    println!("sortat   {:?}: 10 -> {:?}, 50 -> {:?}", v, v.binary_search(&10), v.binary_search(&50));
}

Rezultat

nesortat [20, 50, 40, 10, 30]: 10 -> Err(0), 50 -> Err(5)
sortat   [10, 20, 30, 40, 50]: 10 -> Ok(0), 50 -> Ok(4)

Greșeli frecvente

• Cauți într-un vector nesortat. Nu primești eroare, ci un rezultat fără sens. Sortează întâi sau folosește contains / iter().position().
• Folosești .unwrap() pe rezultat: pentru o valoare care lipsește, programul se oprește. Err nu este o eroare propriu-zisă, ci informația „nu există, s-ar insera aici”.
• Te bazezi pe poziția primită când valoarea apare de mai multe ori. Poate fi oricare dintre ele; pentru prima apariție folosește partition_point.

Comenzi înrudite

• Vec::sort: Sortează vectorul crescător, pe loc. sort este stabilă (păstrează ordinea elementelor egale); sort_unstable e mai rapidă.
• Vec::insert: insert pune un element pe o poziție anume și împinge restul la dreapta; remove scoate elementul de pe o poziție.
• Vec::contains: Verifică dacă vectorul conține un element egal cu valoarea dată; parcurge elementele unul câte unul.
• BTreeSet: Mulțime cu elementele mereu sortate: fără duplicate, ca HashSet, dar parcurgerea este în ordine crescătoare.
• BTreeMap::range: Parcurge doar perechile cu cheile într-un interval (a..b, a..=b, a.., ..b), în ordine crescătoare.