Function binary_search 

pub fn binary_search<T: Ord>(list: &[T], target: &T) -> Option<usize>

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);