Tatu samarqand filiali

Teng bo’lish orqali qidiruv (ikkilik qidiruv) algoritmi

 

Faraz qilaylik,  o’sish tartibida tartiblangan sonlar massivi berilgan bo’lsin. Ushbu 

usulning asosiy g’oyasi shundan iboratki, tasodifiy qandaydir AM element olinadi 

va u X qidiruv argumenti bilan taqqoslanadi. Agar AM=X bo’lsa, u holda qidiruv 

yakunlanadi; agar AM

bo’lgan  barcha  elementlar  kelgusi  qidiruvdan  chiqarib  yuboriladi.  Xuddi 

shuningdek,  agar  AM  >X  bo’lsa,  u  holda  indekslari  M  dan  katta  bo’lgan  

barcha elementlar kelgusi qidiruvdan chiqarib yuboriladi. M  ixtiyoriy  tanlanganda  

ham  taklif  qilinayotgan  algoritm  korrekt  ishlaydi. Shu  sababali  M  ni  shunday  

tanlash  lozimki,  tadqiq  qilinayotgan  algoritm samaraliroq  natija  bersin,  ya’ni  

uni  shunday  tanlaylikki,  iloji  boricha  kelgusi jarayonlarda  ishtirok  etuvchi  

elementlar  soni  kam  bo’lsin.  Agar  biz  o’rtacha elementni, ya’ni massiv 

o’rtasini tanlasak yechim mukammal bo’ladi. Misol uchun butun sonlardan iborat, 

o’sish bo’yicha tartiblangan massivdan ikkilik qidiruv usuli yordamida key kalitga 

mos elementni izlash dasturini ko’rib chiqamiz.   

Dastur kodi: 

#include  

using namespace std;  

int main(){  

    int n;cout<<"n=";cin>>n;  

    int k[n];  

    for(int i=0;i>k[i];  

---

    int key, search;  

    cout<<"qidirilayotgan elementni kiriting=";cin>>key;  

int low = 0;  

int hi = n-1; int j=0;  

while (low <= hi){  

    int mid = (low + hi) / 2;j++;  

    if (key == k[mid]){  

        search = mid;  

        cout<<"qidirilayotgan  element  "<

"<

        system("pause");  

        exit(0);  

    }  

    if (key < k[mid])   

             hi = mid - 1;  

      else low = mid + 1;  

    }  

    search=-1;  

    cout<

topilmadi\n";  

system("pause");  

}       

 

Dastur natijasi  

n=6  

1 2 3 4 5 6  

qidirilayotgan elementni kiriting=6  

qidirilayotgan element 6 o'rinda turibdi va u 3 ta solishtirishda toplidi