Reja: Binar qidirish

Binar izlash
Reja:

1. 
   Binar qidirish.
   
2. 
   Buning uchun eng kam qadamda topish algoritmi qaysi?
   

Binar qidirish — (eng: Binary search — ikkilik qidirish)- saralangan elementlar roʻyxatidan elementni topish uchun samarali algoritm. Ikkilik qidirish algoritmi ishlash gʻoyasiga koʻra „boʻlib tashla va hukmronlik qil“ paradigmasi asosida ishlaydi. Ikkilik qidiruvdan foydalanishning eng keng tarqalgan usullaridan biri bu massivdagi elementni topishdir. Misol uchun, Tycho-2 yulduzlar katalogida bizning galaktikamizdagi eng yorqin 2 539 913 ta yulduz haqida maʼlumot mavjud. Aytaylik, siz yulduz nomidan kelib chiqib, katalogdan maʼlum bir yulduzni qidirmoqchisiz. Agar dastur yulduzlar katalogidagi har bir yulduzni birinchisidan boshlab, chiziqli qidiruv algoritmida tekshirgan boʻlsa, eng yomon holatda kompyuter siz izlayotgan yulduzni topish uchun barcha 2 539 913 ta yulduzni tekshirishi kerak boʻlishi mumkin. Agar katalog yulduz nomlari boʻyicha alifbo tartibida tartiblangan boʻlsa, ikkilik qidiruv, hatto eng yomon holatda ham 22 dan ortiq yulduzni tekshirishi shart emas edi.
Binar qidirish algoritmi ishlash prinsipi
Ikkilik qidirish algoritmining ishlashini tushunish uchun kompyuter bilan oʻyin oʻynab koʻramiz.
Oʻyin sharti

• 
  Kompyuter 1 va 100 oraligʻida ixtiyoriy natural son tanlaydi.
  
• 
  Oldimizda turgan vazifa shu sonni iloji boricha kam taxmin ishlatgan holda topish.
  
• 
  Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter tanlagan sondan katta yoki kichikligini aytadi.
  
• 
  Agar sizning taxminingiz kompyuter tanlagan son bilan bir xil boʻlsa, oʻyin tugaydi.
  

Buning uchun eng kam qadamda topish algoritmi qaysi?
Birinchi navbatda oʻrtadagi sonni taxmin qilib koʻramiz, yaʼni 50 ni. Aytaylik kompyuter bizga taxminimiz kompyuter tanlagan sondan kichikroq ekanligini aytdi. Endi biz kompyuter tanlagan son 51 va 100 orasidagi son ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar oʻrtasidagi sonni olamiz, yaʼni 75 ni. Kompyuter bizga 75 tanlangan sondan katta ekanligini aytdi. Demak, 75 dan katta barcha sonlar ham tanlangan sondan katta ekan. Shunday qilib, bizdagi qidirish sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz oʻylangan sonni topishimiz mumkin. Sonlar 100 ta boʻlgan holatda, biz har qanday tahminni koʻpi bilan 7 ta qadamda topishimiz mumkin boʻladi.
Aytaylik bizga tartiblangan n ta elementdan iborat arr[] massiv berilgan bo'lsin, va berilgan x ni arr[] ichidan qidirish funksiyasini tuzish sharti qo'yilsin.
Bu holatda eng oson yo'l sifatida chiziqli qidiruvni misol keltirish mumkin. Ammo bu usulning vaqt davomiyligi O(n) ni tashkil qiladi. Xuddi shu vazifa uchun biz binar qidir algoritmini ishlatsak bo'ladi.
Dasturi
#include
using namespace std;
int binarySearch(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 binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);

}
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element massivda mavjud emas"
: cout << "Element indeksda mavjud " << result;
return 0;
}

{
if (r >= l) {

int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);

}
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element massivda mavjud emas"
: cout << "Element indeksda mavjud " << result;
return 0;
}

Foydalanilgan adabiyotlar:
https://uz.wikipedia.org/wiki/Binar_qidirish
https://www.texnoman.uz/post/binar-qidiruv-binary-search.html