Function interpolation_search 

pub fn interpolation_search(list: &[i64], target: i64) -> Option<usize>

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