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

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

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.Interpolyatsiya algoritmi