Kalit so'zlari: Chiziqli qidiruv usuli, Binar qidiruv usuli, 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; ifor(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.