O„zbekiston respublikasi aloqa, axborotlashtirish va telekommunikatsiya texnologiyalari davlat qo„mitasi toshkent axborot texnologiyalari universiteti

 
5.3.
 
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 
A
M
 
element 
olinadi  va  u 
X
  qidiruv  argumenti  bilan  taqqoslanadi.  Agar 
A
M
=X
  bo‟lsa,  u  holda 
qidiruv yakunlanadi; agar 
A
M
 
bo‟lsa, u holda indekslari 
M
 dan kichik yoki teng 
bo‟lgan  barcha  elementlar  kelgusi  qidiruvdan  chiqarib  yuboriladi.  Xuddi 
shuningdek,  agar 
A
M
  >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.