“Маълумотлар тузилмаси ва алгоритмлар” фанига кириш

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