Module searching 

Qidiruv algoritmlari (Searching)

Darslik: 03-searching/

Algoritm	Ma’lumot tartiblanganmi?	Time (o’rtacha/eng yomon)	Space
linear_search	Yo’q	O(n) / O(n)	O(1)
binary_search	Ha	O(log n) / O(log n)	O(1)
lower_bound / upper_bound	Ha	O(log n)	O(1)
exponential_search	Ha	O(log i)	O(1)
jump_search	Ha	O(√n)	O(1)
interpolation_search	Ha (tekis taqsimlangan)	O(log log n) / O(n)	O(1)
ternary_search_max	Unimodal funksiya	O(log n)	O(1)

Qaysi birini tanlash?

Ma'lumot tartiblanganmi?
 ├── Yo'q  → linear_search  (yoki avval sort qiling: n log n + log n)
 └── Ha    → binary_search  (99% hollarda to'g'ri javob)
              ├── chegara kerakmi (>=x, >x)? → lower_bound / upper_bound
              ├── massiv juda katta/cheksizmi? → exponential_search
              └── qiymatlar tekis taqsimlanganmi? → interpolation_search

Functions

binary_search

Tartiblangan slicedan target ni topadi va indeksini qaytaradi.

binary_search_answer

Javob ustidan binary search — olimpiada va real hayotdagi eng kuchli usul.

binary_search_recursive

Binary search ning rekursiv ko’rinishi — o’quv maqsadida.

exponential_search

Exponential search — avval oraliqni 1, 2, 4, 8… deb kengaytirib topadi, so’ng shu oraliqda binary search qiladi.

interpolation_search

Interpolation search — qiymatlar tekis taqsimlangan bo’lsa binary searchdan tez.

jump_search

Jump search — tartiblangan massivda √n qadamlab “sakrab” qidirish.

linear_search

Slice bo’ylab boshidan oxirigacha yurib, target ning birinchi indeksini qaytaradi.

linear_search_all

target uchraydigan barcha indekslarni qaytaradi.

linear_search_by

Shart (predikat) bo’yicha qidiradi: shartni qanoatlantirgan birinchi indeks.

lower_bound

Birinchi >= target elementning indeksi (C++ dagi lower_bound).

ternary_search_max

Ternary search — unimodal (avval o’sib, keyin kamayadigan) funksiya maksimumi.

upper_bound

Birinchi > target elementning indeksi (C++ dagi upper_bound).