Qidiruv va xeshlash algoritmlar. Qidiruv algoritmlar: chiziqli algoritm, binary qidiruv algoritmi

Qidiruv va xeshlash algoritmlar. Qidiruv algoritmlar:chiziqli algoritm, binary qidiruv algoritmi.

• 
  Reja:
  
• 
  Qidiruv masalalari. Qidiruv Abstraksiyasi;
  
• 
  Ketma-ket qidiruv algoritmlari;
  
• 
  Oraliqni (hududni) qisqartirish usulida izlash algoritmi;
  
• 
  Taqsimlangan qidirish algoritmlari;
  
• 
  Xesh jadval tushunchasi;
  
• 
  Xeshlash usuli qo’llaniladigan sohalar;
  

Qidiruv masalalari

• 
  Qidiruv masalasini shakllantirish quyidagicha bosqichda amalga oshiriladi:
  
• 
  1-bosqichda. Ma’lumotlarni yig’ish, to’ldirish.
  
• 
  2-bosqichda. Ma’lumotlarni tashkil etish (tartiblash va saralash);
  
• 
  3-bosqichda. Ma’lumotlarni olish (hususiy qidiruv);
  

Talablari:

• 
  Katta hajmli axborotlarni qo’llab quvvatlashi;
  
• 
  Ma’lumotlarni tezkor topish imkoniyati;
  
• 
  Tezkor modifikatsiyalash shuningdek ochirish imkoniyati;
  

Abstraksiyalash uslublari (metodlari)

• 
  – Create xotiraga yangi yozuv qo’yish;
  
• 
  – Read kalit bo’yicha ma’lumotlarni qidirish.
  
• 
  – Update kalit bo’yicha ma’lumotlarni yangilash.
  
• 
  – Delete ma’lumotlarni o’chirish.
  

Umumiy holda qidiruv masalasini quyidagicha talqin etiladi:

• 
  a1, a2, a3,…,an kalitlar to’plami berilgan bo’lsin. key qiymatiga mos bo’lgan kalit indeksini aniqlash.
  
• 
  To’plam a;
  
• 
  index = a.find(key);
  

Mavjud qidiruv algoritmlari

Bizga massiv berilgan bo’sin:

• 
  a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
  
• 
  Ushbu masalani yechishda eng birinchi xayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul:
  
• 
  Chiziqli qidiruv - Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda:
  

Ko'rib turganingizdek, funksiyamiz 2 ta parametr qabul qiladi, birinchisi massivni o'zi, ikkinchisi esa biz qidirayotgan element. Agar uni topa olmasak, "-1" qiymatni qaytaramiz.