Binar qidirish

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.

Binary Search

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.

Binary search tree example

Dasturi

#include <bits/stdc++.h>
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;
}

.