Kalit so'zlari: Chiziqli qidiruv usuli, Binar qidiruv usuli, Interpolyatsiya algoritmi


Download 372.57 Kb.
bet1/2
Sana29.11.2020
Hajmi372.57 Kb.
#154994
  1   2
Bog'liq
2-ma'ruza


2-ma'ruza matni

Kalit so'zlari: Chiziqli qidiruv usuli,  Binar qidiruv usuli, Interpolyatsiya algoritmi

1. Chiziqli qidiruv algoritmi

Bu qidiruv algoritmining asosiy g’oyasi – massivning barcha elementlarini qidirilayotgan kalit-qiymat bilan ketma-ket taqqoslab chiqish va topilgan elementning joylashgan pozitsiyasini qaytrishdan iborat. Shuning uchun ham bu qidiruv usuli odatda ketma-ket qidiruv deb ataladi.

Bu usulda qidiruv algoritmining ish samaradorligi juda past.

Bu algoritmni namunaviy misol yordamida o’rganib chiqamiz. Misol. Tasodifiy sonlar bilan to’ldirilgan massivdan oldindan berilgan kalit-qiymatli elementning joylashgan pozitsiyasi (indeksi)ni aniqlang.

Yechimi:

Buning uchun butun sonli arr[] massivini tavsiflab, uni tasodifiy sonlar generatori rand() funktsiyasi yordamida qiymatlarga to’ldiramiz (misol uchun 50 ta butun son bilan).

Klaviaturadan kiritilgan kalit-qiymatga teng bo’lgan qiymatga teng element massivda bor yoki yo’qligini aniqlash funktsiyasi linSearch() ni tavsiflaymiz.

int linSearch(int arr[], int requiredKey, int arrSize)

{

         for (int i = 0; i < arrSize; i++)

         {

                   if (arr[i] == requiredKey)

                            return i;

         }

         return -1;

}

Massivni ekranga chiqaish funksiyasi showArr():



void showArr(int arr[], int arrSize)

{

         for (int i = 0; i < arrSize; i++)

         {

                   cout << setw(4) << arr[i];

                   if ((i + 1) % 10 == 0)

                   {

                            cout << endl;

                   }

         }

         cout << endl << endl;



}

Chiziqli qidiruv usuli qo’llanilan dastur.

#include

#include

#include

#include

#include

using namespace std;

//funksiy prototipi

int linSearch(int arr[], int requiredKey, int size); // chiziqli qidiruv - k-ket qidiruv

void showArr(int arr[], int size); // massivni ekranga chiqarish funksiyasi

int main()

{

         const int arrSize = 30;



         int arr[arrSize];

         int requiredKey = 0; // qidirilayotgan qiymat (kalit)

         int nElement = 0; // massiv elementining nomeri

         srand(time(NULL));

         //massivga 1 dan 50 gacha bo'lgan tasodifiy sonlarni yozish

         for (int i = 0; i < arrSize; i++)

         {

                   arr[i] = 1 + rand() % 50;

         }                

         showArr(arr, arrSize);

         cout << "Qidirilayotgan qiymatni kirit: ";

         cin >> requiredKey; // ââîä èñêîìîãî ÷èñëà

         //elementni qidirish va uning positsiyasini eslab qolish

         nElement = linSearch(arr, requiredKey, arrSize);

         if (nElement != -1)

         {

                   //agar element topilsa uning pozitsiyasini ekranga chiqarish

cout << "Qidirilayotgan qiymat " << requiredKey << " massivning " << nElement << " -indeksida joylashgan"<

         }

         else

         {

                   //agar element topilmasa

         cout << "Massivda bunday qiymatli son mavjud emas..." << endl;

         }

         return 0;

}

//massivni ekranga chiqarish funksiyasi



void showArr(int arr[], int arrSize)

{

         for (int i = 0; i < arrSize; i++)



         {

                   cout << setw(4) << arr[i];

                   if ((i + 1) % 10 == 0)

                   {

                            cout << endl;

                   }

         }

         cout << endl << endl;

}

//chiziqli qidiruv funksiyasi



int linSearch(int arr[], int requiredKey, int arrSize)

{

         for (int i = 0; i < arrSize; i++)



         {

                   if (arr[i] == requiredKey)

                            return i;

         }

         return -1;

}

Dasturni ishga tushirsak, quyidagi natijani beradi:



Agar massivdan element topilmasa:



Agar dastur ishlashiga etibor bersak ushbu algoritm massivda bir xil qiymatli takrorlanuvchi elementlarning faqat birinchisining indeksini qaytaradi.

Takrorlanuvchi elementlarning barchasini aniqlash va ekranga chiqarish funksiyasini mustaqil o’rganing va ishlatib ko’ring.

Bu algoritmdan elementlarining joylashishi noaniq yoki tartibsiz bo’lgan massivlarga qo’llash aniq samara beradi.

Agar massiv elementlari saralanganligi aniq bo’lsa, u holda bunday massivlardan qidiruv uchun binar qidiruv usulini qo’llash tavsiya etiladi.

2. Binar qidiruv usuli

Biz chiziqli qidiruv algoritmlarini qarab chiqdik. Qidiruvning boshqa algoritmlari ham mavjud. Masalan, ikkilik (binar) qidiruv algoritmi. Biz yuqorida chiziqli qidiruv algorimtlaridan indeksli ketma-ket qidirish usulini qarab chiqdik. Bunda qayta ishlanayotgan tuzilma elementlarini saralangan bo’lishi kerak edi. Xuddi shunday binar qidiruv algoritmi ham saralangan tuzilmalar ustida qo’llanilsa, yuqori samara beradi.

Faraz qilaylik, bizga 12 ta elementdan iborat, o’sish tartibida saralangan quyidagi massiv berilgan bo’lsin:




Foydalanuvchi tomomnidan kiritilgan qidiruv kaliti asosida qidirilayotgan elementni topish masalasi qo’yilgan. Masalan, kalit 4 ga teng.



Birinchi qadamda massiv teng ikkiga bo’linadi (buning uchun o’rta element - midd ni topib olamiz): (0 + 11) / 2 = 5 (bo’linmaning butun qism olinadi, 0.5 tashlab yuboriladi). Birinchi massiv elementlarining o’rta qiymatini tekshiramiz, agar u kalit bilan mos kelsa, algoritm o’z ishini yakunlaydi va topilgan element haqida axborot beradi. Qaralayotgan misolda o’rta qiymat qidirilayotgan kalitga mos kelmaydi.

Agar qidirilayotgan kalit qiymatli element o’rta qiymatdan kichik bo’lsa, algoritm o’rta qiymatdan katta elementlar joylashgan qismini tekshirmaydi. Qidiruvning o’ng tomondagi chegarasi (midd - 1) ga joylashadi. Hosil bo’lgan qism massivni yana 2 ga bo’lamiz.



Qidiruv kaliti yana o’rta elementga teng emas, katta. Endi qidiruvning chap chegarasi (midd + 1) ga joylashadi.

 

Uchinchi qadamda o’rta element 3 indeksli elementga teng: (3 + 4) / 2 = 3. U kalitga teng. Algoritm o’z ishini yakunlaydi.

Misol:

#include



using namespace std;

// binar qidiruv algoritmi funktsiyasi

int Search_Binary (int arr[], int left, int right, int key)

{

         int midd = 0;



         while (1)

         {

         midd = (left + right) / 2;

if (key < arr[midd])       // agar qidirilayotgan element kichik bo’lsa

right = midd - 1;      // qidiruvning o’ng chegarasini aniqlash

else if (key > arr[midd])  // agar qidirilayotgan element katta bo’lsa

         left = midd + 1;        // qidiruvning chap chegarasini aniqlash

         else                       // yoki (qiymat teng)

         return midd;           // funktsiya ushbu yacheyka qiymatini qaytaradi

         if (left > right)          // agar chegara mos kelmasa

                   return -1;

         }

}

int main()



{

int SIZE;

cout << "\n\nMassiv uzunligini kiriting: ";

         cin>>SIZE;

//       const int SIZE = 12;

         int array[SIZE] = {};

         int key = 0;

         int index = 0; // qidirilayotgan qiymatning yacheyka indeksi

         for (int i = 0; i < SIZE; i++) // massivni to’ldirish va ko’rsatish

         {

                   array[i] = i + 1;

                   cout << array[i] << " | ";

         }

         cout << "\n\nIxtiyoriy sonni kiriting: ";

         cin >> key;

                   index = Search_Binary (array, 0, SIZE, key);

         if (index >= 0)

cout << "Ko’rsatilgan son quyidagi indeksli yacheykada joylashgan: " << index << "\n\n";

         else

         cout << "Massivda bunday son mavjud emas!\n\n";

         return 0;

}

Natija:



 

Ikkilik qidiruv ketma-ket (chiziqli) qidiriuv algoritmlaridan samarali hisoblanadi, ya’ni uning qiyinlik bahosi O(log2) ga teng (eslatma, ketma-ket qidiruvda O).

Misol uchun massiv elementlari 1024 ta bo’lsa, eng yomon holat (qidirilayotgan element massivda yo’q bo’lsa) 1024 ta element ham massivda qidirib ko’rilishi kerak, lekin binar qidirish algoritmida log2(1024)=10 elementni ko’rib chiqish yetarli bo’ladi.  Bu birinchi qadamdan keyin 512 ta, ikkinchi qadamdan keyin 256 ta va h.k. elementlar har bir qadamda teng yarmiga qisqarib boraveradi, natijada 10-qadamdan keyin element mavjud emasligi haqidi axborotni chiqaradi.

Bu algoritmning kamligi massiv oldindan saralangan bo’lishi talab etilishidir.

 

3.


Download 372.57 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling