“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Chiziqli qidiruvni amalga oshirish protsedurasi
Chiziqli qidiruv
Indeksli ketma ket qidiruv
Bu ko’rinishdagi qidiruvda 2ta jadval tashkil qilinadi :
1. O’z kalitiga ega ma”lumotlar jadvali( osish tartibida);
2. Indekslar jadvali – bu jadval ham kalitlardan tashkil topgan, lekin bu kalitlar asosiy jadvaldan tanlab aniq interval (m<=n) bilan olinadi.
Dastlab qidiruv argumenti bo’yicha indekslar jadvalida ketma ket qidiruv o’tkaziladi. Tanlangan kalitdan katta kalit topilganda, biz asosiy jadvalda qidiruvning quyi – low-, va yuqori –hi- (kind > key) chegaralarini belgilab qo’yamiz.
Masalan, key=101
Qidiruv jarayoni butun jadval bo’yicha emas, balki low dan hi gacha o’tkaziladi.
Indeksli ketma-ket qidiruv
Eslatma
Indeksli ketma-ket algoritmdan, agar ma’lumotlar jadvali tartiblangan bo‘lsa, foydalanish mumkin bo‘ladi.

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 keyHi=mid-1
Else low=mid+1 endif
Endwhile
Search=0
Return