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

Interpolyatsiya algoritmi

Interpolyatsiya — bu butun soha va qidirilayotgan qiymatga o’xshash elementlar joylashishgan masofani hisoblash orqali qidiruv sohasini aniqlash usuli hisoblanadi. Bunga misol sifatida geometriyadagi o’xshash uchburchaklarni olish mumkin, bunda burchaklar qiymati bir xil, lekin proportsiyasi har xil bo’ladi. Interpolyatsiya usulida ham aynan shunday printsipdan foydalaniladi.

Qidiruv sohasi uzunligi soha boshidan kerakli songacha (masalan, markazdagi elementgacha) masofa hisoblanadi. Hisoblash element nomeri va qiymatlari bo’yicha amalga oshiriladi,  undan keyin aniqlangan soha uzunligi bilan qiymatlar orasidagi uzunlik ko’paytiriladi va natijaga soha boshining qiymati qo’shilib, qidirilayotgan qiymat aniqlanadi.

Buni tushinib olish uchun quyidagicha chizmani olamiz. Bunda 100 ta elementdan iborat massiv berilgan:

Buni hisoblash formulasi juda sodda bo’lib, qidirilayotgan element va birinchi element orasidagi masofa (uzunlik)ni hisoblaydi (misolda 20-1). Xuddi shunday birinchi va oxirgi elementlar orasidagi uzunlik hisoblanadi (misoldagi 100-1). Aniqlangan uzunliklar o’zaro bo’linadi(misoldagi (20-1)/(100-1)) (o’xshashlik sohasi uzunligi va birinchi va oxirgi elementlar orasidagi uzunlikka). Xuddi shunday qiymatlarning chegaralari orasidagi uzunlik ham hisoblanadi (misoldagi 200-5).

Olingan natijalar o’zaro ko’paytriladi va birinchi yacheyka nomeriga ko’paytiriladi. Ya’ni,

1 + (20-1)/(100-1) * (200-5) = 38 (qoldiq bilan).

Olingan natija aynan qidirilayotgan qiymatni beradi. Ya’ni misoldagi №20 nomerda 38 qiymati joylashgan.

#include

#include

#include

#include

#include

using namespace std;

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;

}

void pufak_s (int arr[], int arrSize)

{ 

      int i,j;

      int x;

      for (i=0; i

          for(j=arrSize; j>i; j--)

            if(arr[j-1]>arr[j]) 

                            {

               x=arr[j]; arr[j]=arr[j-1]; arr[j-1]=x;

            }

          }

int main()

{

         //Qidiruv amalga oshiriladigan massiv qiymatlari

         const int arrSize = 50;

         int MyArray[arrSize];

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

         int nElement = 0; // massiv elementining nomeri

         srand(time(NULL));

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

         {

                   MyArray[i] = 1 + rand() % 100;

                   }

         showArr(MyArray, arrSize);

pufak_s(MyArray,arrSize);

  cout<<"Saralangan massiv:\n";

      showArr(MyArray, arrSize);

int x = 0; //massivning qidirilayotgan element bilan

               // taqqoslanatotgan joriy pozitsiyasi

         int a = 0; //qidiruv bajarilayotgan oraliqning chap chegarasi

         int b = arrSize; //qidiruv bajarilayotgan oraliqning o'ng chegarasi

         int WhatFind;

bool found; //element topilganda True qiymatini oluvchi o'zgaruvchi-bayroq

         cout<<"Qidirilayotgan elementni kirit"<

         cin>>WhatFind;

/********* Interpolyatsiya boshlanishi **************************/

for (found = false;

 (MyArray[a] < WhatFind) && (MyArray[b] > WhatFind) && !found; )

{

//Interpolyatsiyani hisoblash

x = a + ((WhatFind - MyArray[a]) * (b - a)) / (MyArray[b] - MyArray[a]);

         //yangi qidiruv oralig'ini hisoblash

                   if (MyArray[x] < WhatFind)  

                            a = x + 1;

                   else if (MyArray[x] > WhatFind)  

                            b = x - 1;

                   else

                            found = true;

         }

/************** interpolyatsiya oxiri ********************/

//Agar qidiruv oralig'idan element topilsa, uning chegarasini ko'rsatish

         if (MyArray[a] == WhatFind)

cout << " Element topildi u " << a <<" -indexda joylashgan  " << WhatFind << " ga teng" <

         else if (MyArray[b] == WhatFind)

cout << " Element topildi u " << b <<" -indexda joylashgan  " << WhatFind << " ga teng"<< endl;

         else

                   cout << "Kechrasiz element mavjud emas!!! " << endl;

         return 0;

}

Interpolyatsiya qidiruv usuli binar qidiruv g’oyasining ba’zi elementlarini o’z ichiga oladi. Bu qidiruv usuli ham saralangan massivlarda qo’llash uchun mo’ljallangan. Bu qidiruv usulining binar qidiruvdan asosiy farqi, bunda nafaqat sonli qiymatlarni balki matnli axborotlarni ham qidirish mumkin.

Foydalanilgan manbalar:

1. Алфред В. Ахо., Джон Э. Хопкрофт, Джефри Д. Ульман. Структура данных и алгоритмы. //Учеб.пос., М.: Изд.дом: "Вильямс", 2000, — 384 с.

2. Adam Drozdek. Data structures and algorithms in C++. Fourth edition.Cengage Learning, 2013. 

3. Narzullaev U.X., Qarshiev A.B., Boynazarov I.M. Ma’lumotlar tuzilmasi va algoritmlar. //O’quv qo’llanma. Toshkent: Tafakkur nashriyoti, 2013 y. – 192 b.