Reja qidiruv tushunchasi va uning vazifasi Chiziqli qidiruv (kerma –ket ) Indeksli ketma ket qidiruv

Indeksli ketma-ket qidiruv protsedurasi psevdokodi:

• i=1
• While (i<=m) and (kind(i)<=key) do
• i=i+1
• Endwhile
• If i=1 tnen low =1
• Else low=pind(i-1)
• Endif
• If i=m+1 then hi=n

Else hi= pind(i)-1

• Else hi= pind(i)-1
• Endif
• For j=low to hi
• If key=k(j) then
• Search=j
• Return
• Endif
• Next j
• Search=0 return

• Binar (oraliqni teng ikkiga bo‘lish orqali) qidiruv

• Algoritm g’oyasi

• Berilgan massiv o‘rtasidagi element olinadi, ya’ni am (m=(N+1)/2), va u X qidiruv argumenti bilan taqqoslanadi. Agar am=X bo‘lsa, u holda qidiruv yakunlanadi; agar am m dan kichik yoki teng bo‘lgan barcha elementlarni kelgusi qidiruvdan chiqarib yuboriladi. Xuddi shuningdek, agar am >X bo‘lsa.

• Izoh

• Mazkur ko‘rinishdagi algoritmdan faqatgina ma’lumotlar jadvali tartiblangan bo‘lsagina foydalanish mumkin.

• Faraz qilaylik, o‘sish tartibida tartiblangan sonlar massivi berilgan bo‘lsin, ya’ni a1 ≤ a2 ≤ a3 ≤… aN .
• X- qidiruv kaliti bo‘lsin.

• Low=1
• Hi=n
• While (low<=hi) do
• mid=(low+hi)div2
• If key=k(mid) then
• Search=mid
• Return
• Endif
• If key
• Hi=mid-1
• Else low=mid+1 endif
• Endwhile
• Search=0
• Return

• Binar qidiruv protsedurasi psevdokodi

Misol. Klyuchi 52 ga teng bo’lgan element topilsin.

• Birinchi taqqoslanadigan element 49 bo’ladi 49<52,shuning uchun keyinggi o’rta
• qiymatni 49dan
• yuqorida
• joylashgan
• elementlarlar
• orasidan
• qidiramiz.Bu 86.

. Taqqoslaymiz: 86>52, shuning uchun endi 52 ni 86dan pastda,49dan yuqorida yani [49;86] da qidiramiz. Keyingi qadamda navbatdagi o’rta qiymat 52ga tengligi aniqlaymiz. Shunday qilib, 52ga teng element topildi.

• Demak : key=52 bo’lganida yozuv
• 3ta taqqoslashda topildi.
• Taqqoslash uchun :
• key=101bo’lganida ham yozuv
• 3ta taqqoslashda topiladi.

• Agar C—taqqoslashlar soni desak, n- elementlar soni bo’lsa, u holda C=log n (asosi 2).
• Misol uchun n=1024bo’lsa,
• binary qidiruvda C=10,
• ketma ket qidiruvda C=512