“Ахборот технологиялари” факультети “Ахборот технологияларини дастурий таъминоти” кафедраси “маълумотлар тузилмаси ва алгоритмлар”

Тенг бўлиш орқали қидирув (иккилик қидирув). 
Фараз қилайлик, ўсиш тартибида тартибланган сонлар массиви берилган бўлсин. Ушбу усулни асосий 
ғояси шундан иборатки, тасодифий қандайдир A
M 
элемент олинади ва у Х қидирув аргументи билан 
таққосланади. АгарA
M
=Х бўлса, у ҳолда қидирув якунланади; агар A
M
кичик ёки тенг бўлган барча элементларни келгуси қидирувдан чиқариб юборилади. Худди шунингдек, агар A
M
>X бўлса. 
М ихтиёрий танланганда ҳам таклиф қилинаётган алгоритм коррект ишлайди. Шу сабабали М ни 
шундай танлаш лозимки, тадқиқ қилинаётган алгоритм самаралироқ натижа берсин, яъни уни шундай 
танлайликки, иложи борича келгуси жараёнларда иштирок этувчи элементлар сони кам бўлсин. Агар биз ўртача 
элементни, яъни массив ўртасини танласак ечим мукаммал бўлади.
алгоритм 
low := 1; 
hi := n; 
while (low <= hi) do 
begin 
mid := (low + hi) div 2; 
if key = k[mid] then 
begin 
search := mid; 
exit; 
end; 
if key < k[mid]
then hi := mid - 1 

---

31
else low := mid + 1; 
end; 
search := 0; 
exit; 
ҚИДИРУВ ЖАДВАЛИНИ ҚАЙТА ТАРТИБЛАШ 
Умуман олганда, жадвалда хар бир элементни қидириш эхтимоллигини қандайдир бир қиймат билан 
изоҳлаш мумкин. Фараз қилайлик жадвалда қидирилаётган элемент мавжуд. У ҳолда қидирув амалга 
оширилаётган барча жадвални дискрет холатга эга тизим сифатида қараш мумкин хамда унда қидирилаётган 
элементни топиш эхтимоллиги – бу тизим i-чи холати эхтимоллиги p(i) деб олиш мумкин.



n
1
i
1
i
p )
(
Жадвални дискрет тизим сифатида қараганимизда, ундаги таққослашлар сони дискрет тасодифий 
миқдорлар қийматларини математик кутилмасини ифодалайди. 
Z=Q=1*p(1)+2*p(2)+3*p(3)+…+n*p(n)
 
Маълумотлар жадвали қуйидаги кўринишда тортибланган бўлиши лозим:
p(1)

p(2) 

p(3) 

…

p(n). 
Бу шарт таққослашлар сонини камайтириб, самарадорликни оширади. Сабаби, кетма-кет қидирув 
биринчи элементдан бошланганлиги учун энг кўп мурожаат қилинадиган элементни биринчига қўйиш лозим. 
Қидирув жадвалини қайта тартиблашни энг кўп ишлатиладиган иккита усули мавжуд. Уларни бир 
боғламли рўйхатлар мисолида кўриб чиқамиз. 
1. Топилган элементни рўйхат бошига қўйиш орқали қайта тартиблаш. 
2. Транспозиция усули.