Reja: Qidir

Binar yoki oraliqni teng ikkiga bo'lish orqali qidiruv (Binary search)

Binar yoki oraliqni teng ikkiga bo'lish orqali qidiruv (Binary search)

II Binar qidiruv funktsiyasi
int search(int arr[], int N, int key)
{
int L=O, R N- 1, mid (L+R)/2; while (L< R)
{
if (arr[mid] = key) return mid; if (arr[mid] < key) L=mid+ 1; else R = mid- 1;
mid (L+R)/2;
}
II dasturda funktsiyadan
11foydalanish misoli

int main O

{
int A[5] = {10,20,30,40,50};
coot << search (A,5,25);
return O;
}

O'tish yoki o'tqazishlar orqali qidiruv

(Jump search)
lzoh: algoritmdan faqatgina ma'lumotlar jadvali tartiblangan bo'Jsagina foydalanish mumkin.
ALGORITM G'OYASI:
Belgilangan bosqichlarda sakrash, ya'ni elementlarning ba'zi bloklarini o'tkazib yuborish orqali (chiziqli qidiruvdan ko'ra) kamroq elementlarni tekshirishdir. Bloklarni o'tqazish uchun qadami ildiz osti N-ga teng. N - ma'lumotlarning umumiy soni.
• • •

Interval Search

Linear Search

2 3 4 5 6 7 8 9

Is 5 >= 78 ? False Is 26 >= 78 ? False Is 107 >= 78 ? True

@ ©JTIITTJ Key = 78

53

78

107

7 8 9

Index of 78 is 8

O'tish yoki o'tqazishlar orqali qidiruv
(Jump search)

II O'tish qidiruv funktsiyasi
int search(int arr[], int n, int key)
{
int i= 0, m = sqrt(n);
while (a[m] <= key && m < n)
{
i= m; m += sqrt(n);
if (m > n - l) return -1;
}
for (int x = i; x if (a[x] = key) return x; return -1;
}
L U UUU UE) \JU UU U _
II dasturda funktsiyadan
11foydalanish misoli

int main ()

{
int A[5] = {10,20,30,40,50};
coot << search (A,5,25); return O;
}

Qidiruv algoritmlari samaradorligi
va mukamallashtirish usullari

• 
  kalit_.larni taqqoslashlar son1;
  
• 
  dasturning ishlab chiqishga ketgan vaqt;
  

Qidiruv
algoritmlarining

• 
  dasturni ishlashi uchun ketgan vaqt;
  

samaradorlik

• 
  tala_.
  

b_.qilinadigan xotira

mezonlari
xaJml.

Qidiruv algoritmlari ishlab chiqilayotganida, ko'proq, jadvaldagi kalitlami taqqoslashlar soniga (C) e'tibor qaratiladi.

Algoritmlar samaradorligi
Chiziqli qidiruv algoritmi
Cmin = 1, Cmax = N, Co'rtacha = (N+1)/2.
Algoritm tartibi - chiziqli hisoblanadi - O(N) belgilanadi.


Binar qidiruv algoritmi
Cmin = 1, Cmax = log2(N)
Algoritm tartibi - logarifmik hisoblanadi - O(logN)
belgilanadi.


O'tish qidiruv algoritmi
p - qadam o'lchovi Paptimat = j;;_
cmin = 1+1, cmax = '\/n + '\/n
Algoritm tartibi - O('\f n) belgilanadi.
@ru[TI]

Chiziqli qiduruvni Mukamallashtirish usullari
Y Topilgan elementni jadval boshiga qo 'yish orqali jadvalni qayta tartiblash;
Y Transpozitsiya usuli.

Birinchi usulni mag'zi shundan iboratki, berilgan kalitga teng kalitli element jadvalda birinchi element deb o'zlashtiriladi, qolganlari esa suriladi.
Keltirilgan algoritm ro'yxat uchun ham massiv uchun xam o'rinli. Biroq bu algoritm massiv uchun tavsiya qilinmaydi, sababi elementlarni o'rinlashtirishga ko'rsatkichlarni o'rinlashtirishdan ko'ra ancha ko'p vaqt talab qiladi.


Transpozitsiya usulida topilgan element jadvalda bitta oldingi element bilan o'rin almashtiriladi. Agarda mazkur elementga ko'p murojaat qilinsa, bittadan oldinga surilib borib natijada jadval boshida bo 'ladi.
Ushbu usul nafaqat ro'yxatda, balki massivda xam ula (sababi faqatgina ikkita yonma-yon turgan element o'rin almashti 1
@ru[TI]