3-amaliy mashg’ulot mavzu: Taqribiy integrallash usullari. Zaruriy aniqlikni ta’minlovchi qadamni tanlash. Qidiruv algoritmlari: chiziqli va binary qidiriruv

3-AMALIY MASHG’ULOT
Mavzu: Taqribiy integrallash usullari. Zaruriy aniqlikni ta’minlovchi qadamni tanlash. Qidiruv algoritmlari: chiziqli va binary qidiriruv.
Kompyuterda ma’lumotlarni qayta ishlashda qidiruv asosiy amallardan biri hisoblanadi. Uning vazifasi berilgan argument bo’yicha massiv ma’lumotlari ichidan mazkur argumentga mos ma’lumotlarni topish yoki bunday ma’lumot yo’qligini aniqlashdan iboratIxtiyoriy ma’lumotlar majmuasi jadval yoki fayl deb ataladi. Ixtiyoriy ma’lumot (yokituzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noyob bo’lishi, ya’ni mazkur kalitga ega ma’lumot jadvalda yagonabo’lishi mumkin.
Qidiruv algoritmlarining binary va chiziqli qidiruv usullarini ko’rib chiqamiz:
Aytaylik bizga massiv berilgan:
a[]={5,8,1,2,13,7,9,10,11,6};
Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan dastur tuzish sharti qo'yilgan. Ushbu masalani yechishda eng birinchi xayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul:
Chiziqli qidiruv - Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda:
#include

using namespace std;
int chiziqli_qidiruv(int array[], int size, int searchValue)
{ for(int i =0; i < size; i++)
{ if(searchValue == array[i]) {
return i;
}} return-1;}

int main()
{
int a[]={15,58,96,78,45,96};
int qid_son;
cout<<"Qidirilayotgan sonni kiriting: "<<" ";
cin>>qid_son;
int natija = chiziqli_qidiruv(a, sizeof(a), qid_son);
if(natija >=0)
{ cout<<"Qidirilayotgan son "<< a[natija]<<" "<< natija <<"- indexda joylashgan"<< endl;
}
else
{ cout<<"Qidirilayotgan son "<< qid_son <<" ushbu massivda mavjud emas. "<< endl;
}}
Endi bundan optimal bo'lgan usul - binar(ikkilik) qidiruvni ko'rib chiqsak. Bu usulda ham funksiyaga 2 ta parametr, birinchisi massiv o'zi keyin esa biz qidirayotgan elementni parametr sifatida beriladi. Qidiruv esa quyidagicha: Dastlab biz massiv boshi va oxirini o'zimiz uchun o'zgaruvchilarda belgilab olamiz, mening kodimda bu left va right o'zgaruvchilaridir:

• left va right index lari markazidagi elementni topamiz (left + right) / 2
• topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
• agar a[mid] elementimiz biz qidirayotgan elementdan kichkina bo'lsa biz left = mid deb belgilaymiz va shunda a[mid:right] bo'lagida qidiruv davom etadi.
• agar a[mid] elementimiz biz qidirayotgan elementdan katta bo'lsa demak right = mid deb belgilaymiz shunda qidiruv a[left:mid] bo'lagida qidiruv davom etadi.

Shu zaylda qidiruv left < right shart bajarilmagunicha davom etadi, agar bu jarayonda biz qidirgan element topilmasa u xolda -1 javob qaytariladi, quyida dastur kodi keltirilgan:

#include
int binarqidiruv(int arr[], int l, int r, int x)
{ if (r >= l)
{ int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarqidiruv(arr, l, mid-1, x);
return binarqidiruv(arr, mid+1, r, x);
} return -1; }
int main(void)
{ int arr[] = {2, 3, 4, 10, 40,20};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 1;
int natija = binarqidiruv(arr, 0, n-1, x);
(natija == -1)? printf("X soni massivni ichidan topilmadi.")
: printf("X soni massivning %d - elementi.",
natija); return 0;
}