Binar search (Ikkilik qidiruv)

Nazariy Qism

Ta'rif

Ikkilik qidiruv (eng: Binary search — ikkilik qidiruv)- saralangan elementlar roʻyxatidan elementni topish uchun samarali algoritmlardan biri hisoblanadi. Ikkilik qidiruv algoritmi ishlash gʻoyasiga koʻra "boʻlib tashla va hukmronlik qil" paradigmasi asosida ishlaydi.

Bu algoritmni tushunishdan oldin oddiy chiziqli qidiruv (Linear search) haqida gaplashamiz.

Chiziqli qidiruv (Linear search)
Chiziqli qidiruv algoritmi oddiy algoritm bo'lib, u ro'yxatdan element qidirganida ro'yxatdagi barcha elementga murojat qilib chiqadi. Bunday holatda algoritmning vaqt murakkabligi eng yaxshi holati O(1) va eng yomon holati esa O(n) ga teng bo'ladi, bu esa real hayotda juda yomon natija hisoblanadi.
Tasavvur qilaylik Instagramning 1 mlrd dan ziyod foydalanuvchisi bor va foydalanuvchi o'z profiliga kirmoqchi. Bunda Instagram foydalanuvchi loginini chiziqli qidirishdan foydalanib tekshiradigan bo'lsa va bunda kompyuter sekundiga 10⁶ ta loginni tekshirgan taqdirda ham, o'sha foydalanuvchi profiliga kirishi uchun 1000 soniya (16.6 daqiqa) kutishi kerak bo'lardi. Shu sababli ham bunday holatlar uchun bizga samaraliroq algoritmlar kerak bo'ladi.

Ikkilik qidiruvning ishlash pirinsipi
Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling do'stimiz bilan o'yin o'ynab ko'ramiz. O'yin shartlari quyidagicha:

• Do'stimizga 1 dan 50 gacha bo'lgan sonlar orasidan bitta sonni o'ylashini aytamiz. Siz esa do'stimiz o'ylagan sonni iloji boricha kamroq urinishda topishingiz kerak bo'ladi.
• Har bir taxminingizdan so'ng do'stimiz sizga o'ylagan soni siz taxmin qilgan sondan kichik yoki katta ekanligini aytadi va siz yana taxmin qilishda davom etasiz..
• Agar siz taxmin qilgan son do'stimiz o'ylagan son bilan bir xil bo'lsa o'yin tugaydi.

Do'stimiz 36ni o'yladi.
Xo'sh bunday holatda nima qilamiz ?

1. Albatta, birinchi bo'lib o'rtadagi sonni tanlaymiz ya'ni 25, do'stimiz bu son o'zi o'ylagan sondan kichik ekanligini aytadi va biz endi qidirilyotgan sonni [26 - 50] oraliqdan qidiramiz.
2. Ikkinchi taxminimizda biz 38 ni tanlaymiz, do'stimiz esa bu son o'zi o'ylagan sondan katta ekanligini aytadi. Endi biz u o'ylagan sonni [26 - 37] oralig'idan qidiramiz.
3. Uchinchi urinishimizda biz 31 ni tanlaymiz, u esa bu son o'zi o'ylagan sondan kichkina ekanligini aytadi. Biz oraliqni [32 - 37] qilib olamiz va qidirishda davom etamiz.
4. To'rtinchi urinishimizda biz 35 sonini taxmin qilamiz va u bu son ham o'zi o'ylagan sondan kichkina deb aytadi endi u o'ylagan son 35 dan katta va 37dan kichik ekanligi malum bo'ladi.
5. Ushbu oraliqda bitta 36 soni borligi uchun biz unga sonini o'ylaganligini aytamiz va o'yinni yakunlaymiz.

Demak biz 1 dan 50 gacha oraliqda yashirin sonni topish uchun 5tagina urinish qildik, agar bu sonni biz chiziqli qidirganimizda 36ta urinish qilar edik.

Algorithm Murakkabligi
Algoritmning murakkabligi Time (vaqt) miqdori asosida o'lchanadigan qiymat. Bunda Time dasturning ishlash jarayonida ketqizadigan vaqti. Bu faktor algoritmni effektivligini aniqlaydi. Yaxshi algoritmlarda Time kam miqdorda bo'ladi, bu esa usha algoritmda yozilgan kodning ishlash tezligini oshiradi.

Algoritmlarni tahlil qilishni yana Asymptotic analysis ham deyiladi. Bunda kiritilgan input kattaligiga qarab algoritmning ishlash vaqti hisoblanadi.

Asymptotic analysis ga misol sifatida tartiblangan array'dan berilgan X sonni topish uchun Linear Search va Binary Search algoritmlarini taqqoslaymiz.

Linear search siklda arrayning birinchi elementidan boshlab X ni topguncha array elementlarini bittalab tekshirib chiqadi. Array uzunligini N deb oladigan bo'lsak, X ni topish uchun minimal 1 maksimal, N solishtirishni amalga oshiradi.
Binary Search ro'yxatning o'rtasidagi element qiymatini – M ni oladi va uni X bilan solishtiradi:

• X M ga teng bo'lsa, bingo! birinchi urinishdayoq kerakli element topildi.
• Agar X M dan kichik bo'lsa, demak qidirishni ro'yxatning birinchi yarmidan davom ettirish kerak.
• Agar X M dan katta bo'lsa, demak qidirishni ro'yxatning ikkinchi yarmidan davom ettiriladi.

Hudi shunday uslubda, avval qismning o'rtasi M topiladi, keyin X ni M bilan solishtirib boriladi.
Biz 100 000 elementi bor katta ro'yxatni oladigan bo'lsak:
Binary Search orqali minimal 1ta, maksimal Log(100000) bu 16ga teng urinish degani. Linear Searchda esa minimal 1ta maksimal esa 100 000 urinish qiladi.

• Linear searchda maksimal 100,000 urinish
• Binary searchda maksimal 16 urinish!

Biz aytib o'tgan urinishlar sonini aniqlashda ko'pincha best case(eng yaxshi holat), average case(o'rtacha holat) va worst case(eng yomon holat)lar orqali hisoblanadi.
Best case va worst case grekcha Θ harfi bilan yoziladi.

Linear search va binary search algoritmlari Θ da yozilganda:

Best case:

• – linear search – Θ(1)
• – binary search – Θ(1)

Worst case:

• – linear search – Θ(n)
• – binary search – Θ(log n)

Amaliy Qism

Bizga Nta quydagicha tub sonlar ro'yxati berilgan bo'lsin va biz ushbu sonlar ro'yxatidan ro'yxatda qiymati Xga teng bo'lgan sonning joylashgan o'rnini topish muommosi qo'yilgan bo'lsin:
N = 17
X = 37

Biz ushbu muommoni birinchi chiziqli qidiruv (linear search) usulida qidirib ko'ramiz.

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int N, X;
    cin >> N >> X;
    int a[N];
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }
    //agar berilgan ro'yxatimiz tartiblanmagan bo'lsa uni birinchi tartiblab olamiz
    sort(a, a + N);
    for(int i = 0; i < N; i++){
        if(a[i] == X){
            cout << i << endl;
            break;
        }
    }
    
    return 0;
}

Endi xuddi shu muommoni ikkilik qidiruv (binary search) orqali yechib ko'ramiz:

#include <iostream>
#include <algorithm>
using namespace std;
int binary_search(int a[], int n, int x){
    int l = 0, r = n-1;
    while(r > l){
        int mid = (l+r) >> 1;
        if(a[mid] < x){
            l = mid + 1;
        }
        if(a[mid] > x){
            r = mid - 1;
        }
    }
    return l;
}
int main(){
  int n, x;
  cin >> n >> x;
  int a[n];
  for(int i = 0; i < n; i++){
      cin >> a[i];
  }
    //agar berilgan ro'yxatimiz tartiblanmagan bo'lsa uni birinchi tartiblab olamiz
  sort(a, a + n);
  cout << binary_search(a, n, x);
  return 0;
}