Topilgan elementni ro’yxat boshiga qo’yish usulida qidiruv algoritmini tushuntirib bering

• Bu usulda topilgan element ro’yxatda o’zidan bitta oldingi element bilan o’rin almashtiriladi. Agarda mazkur elementga ko’p murojaat qilinsa, bittadan oldinga surilib borib natijada ro’yxat boshiga o’tkaziladi.

  
  

• Bu yerda, r – ishchi ko’rsatkich, q – yordamchi ko’rsatkich (r dan bitta qadam keyingi), s - yordamchi ko’rsatkich (q dan ikkita qadam keyingi)

  
  

Ushbu usul nafaqat ro’yxatda, balki massivda ham qulay (sababi faqatgina ikkita yonma-yon turgan element o’rin almashtiriladi).

• Biz chiziqli qidiruv algoritmlarini qarab chiqdik. Qidiruvning boshqa algoritmlari ham mavjud.

  
  

• Masalan, ikkilik (binar) qidiruv algoritmi.

  
  

• Biz yuqorida chiziqli qidiruv algorimtlaridan indeksli ketma-ket qidirish usulini qarab chiqdik. Bunda qayta ishlanayotgan tuzilma elementlarini saralangan bo’lishi kerak edi.

  
  

• Xuddi shunday binar qidiruv algoritmi ham saralangan tuzilmalar ustida qo’llanilsa, yuqori samara beradi.

  
  

• Faraz qilaylik, bizga 12 ta elementdan iborat, o’sish tartibida saralangan quyidagi massiv berilgan bo’lsin:

  
  

• Foydalanuvchi tomonidan kiritilgan qidiruv kaliti asosida qidirilayotgan elementni topish masalasi qo’yilgan. Masalan, kalit 4 ga teng bo’lsin.

  
  

• Agar C – taqqoslashlar soni va n – jadvaldagi elementlar soni bo’lsa, u holda

  
  

• Masalan, n = 1024, bo’lsa,

  
  

Ketma-ket qidiruvda C = 512, binar qidiruvda esa C = 10.

• Agar katta hajmdagi ma’lumotlar ichida qidiruv amalga oshirilayotgan bo’lsa, u holda binar va indeksli ketma-ket qidiruvni umumlashtirib olib borish mumkin. Sababi, har ikkala qidiruv ham tartiblangan massivda amalga oshiriladi.

  
  

Bu algoritmning kamchiligi massiv oldindan saralangan bo’lishi talab etilishidir.