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

int search(int arr[], int N, int key)
{
int L=0, 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;
}
return -1;
}
// dasturda funktsiyadan
// foydalanish misoli
int main ()
{
int A[5] = {10,20,30,40,50};
cout << search (A,5,25);
return 0;
}

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

Izoh: algoritmdan faqatgina maʼlumotlar jadvali tartiblangan boʼlsagina 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.

Key = 78

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

// 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 - 1) return -1;
}
for (int x = i; xif (a[x] == key) return x;
return -1;
}
// dasturda funktsiyadan
// foydalanish misoli
int main ()
{
int A[5] = {10,20,30,40,50};
cout << search (A,5,25);
return 0;
}

Qidiruv algoritmlari samaradorligi va mukamallashtirish usullari

Qidiruv algoritmlarining samaradorlik mezonlari

• kalitlarni taqqoslashlar soni;
• dasturning ishlab chiqishga ketgan vaqt;
• dasturni ishlashi uchun ketgan vaqt;
• talab qilinadigan xotira xajmi.

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