11-Amaliy mashg’ulot: Izlash masalasi uchun algoritmlar va ularning murakkabliginq aniqlash

 
 
2. Indeksli ketma-ket qidiruv 
Mazkur koʻrinishdagi qidiruv amalga oshirilaѐtganda ikkita jadval tashkil qilinadi: oʻz
kalitiga ega maʻlumotlar jadvali (oʻsish tartibida tartiblangan) va indekslar jadvali, bu xam 
maʻlumotlar kalitidan iborat- u, lekin bu kalitlar asosiy jadvaldan aniq bir interval orqali 
olingan. (2-chizma). Boshida berilgan argument boʻyicha ketma-ket qidiruv indekslar
jadvalida amalga oshiriladi. Qachonki, biz berilgan kalitdan kichik kalitni
aniqlaganimizda, asosiy jadvalda qidiruvni quyi chegarasini oʻrnatamiz - low, keyin esa 
yuqori chegarani - hi, yaʻni ( kind > key ). Masalan, key = 101. Qidiruv toʻla jadval boʻyicha 
emas, balki low dan hi gacha davom etadi. 

---

3. Ketma-ket qidiruvni samaradorligi 
Ixtiѐriy qidiruvning samaradorligi jadvaldagi maʻlumotlarning kalitlari bilan
solishtirish soni – S bilan baxolanishi mumkin. Agar taqqoslashlar (solishtirish) soni
qancha kichik boʻlsa, qidiruv algoritmi samaradorligi shuncha yaxshi boʻladi. Massivda 
ketma-ket qidiruvning samaradorligi quyidagicha boʻladi: C = 1 n, C = (n + 1)/2. Umuman 
olganda roʻyxatda xam samaradorlik yuqoridagi kabi boʻladi. Garchi massivda xam 
bogʻlangan roʻyxatda xam qidiruv samaradorligi bir xil boʻlsada, maʻlumotlarni massiv va 
roʻyxat koʻrinishda tasvirlashning oʻziga xos kamchilik va afzalliklari mavjud.
Qidiruvning maqsadi - quyidagi jaraѐnlarni bajarilishidan iborat:
1) Topilgan ѐzuvni oʻqish.
2) Qidirilaѐtgan ѐzuv topilmasa, uni jadvalga qoʻyish.
3) Topilgan ѐzuvni oʻchirish. 
Birinchi jaraѐn (qidiruvning oʻzi) massiv uchun ham roʻyxat uchun ham bir xil
boʻladi. Ikkinchi va uchinchi jaraѐnda esa qidiruv roʻyxatli tuzilmada samaraliqroq
boʻladi (sababi massivda elementlarn siljitish lozim). Agar k massivda elementlarni 
siljitishlar soni boʻlsa, u xolda k = (n + 1)/2 boʻladi.