Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti farg‘ona filiali

Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda:
#include
usingnamespace std;
int linearSearch(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, 23, 7, 45, 87, 16};
int userValue;
cout<<"Enter an integer: "<< endl;
cin>> userValue;
int result = linearSearch(a, 6, userValue);
if(result >=0)
{ cout<<"The number "<< a[result]<<" was found at the"
" element with index "<< result << endl; }
else { cout<<"The number "<< userValue <<" was not found. "<< endl;} }


Ko'rib turganingizdek, funksiyamiz 2 ta parametr qabul qiladi, birinchisi massivni o'zi, ikkinchisi esa biz qidirayotgan element. Agar uni topa olmasak, "-1" qiymatni qaytaramiz.
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 := 0 right := len(a)
so'ngra quyidagi shart bajarilgan holda
left< right
quyidagi ketma-ket operatsiyalarni amalga oshiramiz

1. 
   left va right index lari markazidagi elementni topamiz (left + right) / 2
   
2. 
   topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
   
3. 
   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.
   
4. 
   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
Using namespace std;
int binarySearch(int array[], int size, int searchValue)
{
int low =0;
int high = size -1;
int mid;
while(low <= high)
{
mid =(low + high)/2;
if(searchValue == array[mid])
{
return mid;
}
elseif(searchValue > array[mid])
{
low = mid +1;
}
else
{
high = mid -1;
}
}
return-1;
}
int main()
{
int a[]={12, 22, 34, 47, 55, 67, 82, 98};
int userValue;
cout<<"Enter an integer: "<< endl;
cin>> userValue;
int result = binarySearch(a, 8, userValue);
if(result >=0)
{
cout<<"The number "<< a[result]<<" was found at the"
" element with index "<< result << endl;
}
else
{
cout<<"The number "<< userValue <<" was not found. "<< endl;
}
}

Bu usul binar qidiruvni iterativ usuli deyiladi, shuningdek bu algoritmni rekursiya usulida ham yozish mumkin, rekursiv usulni erinmasangiz o'zingiz yozib ko'ring. Bitta urinishda ko'pchilik dasturchilar bu narsani to'g'ri yoza olishmaydi va bu normal holat, chunki xato bor joyda o'z ustida ishlash uchun imkoniyat bo'ladi.

Endi bu qidiruv usullarini ayrim jihatlarini keltirib o'tamiz:

1. 
   funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q
   
2. 
   chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n)
   

Bundan tashqari massivda qidirishning boshqa usullari ham mavjud bu haqida bu yerda batafsil bilib olishingiz mumkin.




Xulosa
Xulosamning qisaqacha mazmuni shundan iboratki Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki massivning elementlari qolmaguncha.






Biz bitta taqqoslashdan so'ng massivning yarim elementlarini hisobga olmasak ham bo'ladi.
1. x ni o'rtadagi element bilan solishtiramiz.
2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz.
3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda.
4. Aks holda chap yarmi bilan binar qidiruvni amalga oshiramiz.