Мундарижа Кириш

2.1.2. Иккилик дарахт бўйича қидириш
Мақсад қийматни сараланган рўйхатнинг ўртадаги қиймати билан солиштириш уч хил натижа бериши мумкин: қийматлар тенг, мақсад қиймати рўйхат элементидан кичик ва мақсад қиймати рўйхат элементидан катта. Биринчи ва энг яхши ҳолда қидириш тугайди. Қолган икки ҳолда рўйхат ярмини ташлаб юборишимиз мумкин.
Агар мақсад қиймати ўрта элементдан кичик бўлса, у ҳолда у бу ўрта элемент олдида жойлашган бўлади. Агар у ўрта элементдан катта бўлса, у ҳолда у ўрта элементдан кейин жойлашган бўлади. Бу рўйхат ярмини ташлаб юборишга етарлича сабаб бўлади. Бу жараённи такрорлаб биз рўйхатнинг қолган қисмларини ярмини ташлаб юборишимиз мумкин. Натижада қуйидаги алгоритмга келамиз:
BinarySearch(list,target,N)
list кўриладиган рўйхат
target мақсад қиймати
N рўйхат элементлари сони
start=1
end=N
while start<=end do
middle=(start+end)/2
select(Compare(list[middle],target)) from
case -1: start=middle+1
case 0: return middle
case 1: end=middle-1
end select
end while
return 0

Бунда Compare(х,у) функцияси -1, 0 ёки 1 қийматларни мос ҳолда x, x=y ёки x>y шартларда беради. Алгоритмлар таҳлилида Compare функцияни чақириш бир солиштириш деб ҳисобланади.

Ушбу алгоритмда агар мақсад қиймат топилган ўрта элементдан катта бўлса start ўзгарувчи middle қийматидан 1 га ошиққа таъминланади. Агар мақсад қиймат топилган ўрта элементдан катта бўлса end ўзгарувчи middle қийматидан 1 га камга таъминланади. Силижиш 1 эса ўрта элемент изланаётган қийматга тенг бўлмаган ҳол билан тушунтирилади.
Цикл ҳар доим тўхтайдими? Агар мақсад қиймат топилса буни return оператори таъминлайди. Агар керакли қиймат топилмаса, у ҳолда ҳар бир цикл итерациясида ё start нинг қиймати ошади ё end ўзгарувчининг қиймати камаяди. Бу уларнинг қиймати бир бирига яқинлашишини кўрсатади. Қандайдир вазиятда улар тенглашади ва цикл start=end=middle да яна бир бор бажарилади. Бу ўтишдан кейин (агар қидирилаётган элемент ушбу индексга мос келмаса) ё start қиймати middle ва end лардан 1 га катта бўлади, ё тескариси, end ўзгарувчи middle ва start лар қийматидан 1 га кам бўлади. Икки ҳолатда ҳам цикл while ёлғон бўлади ва цикл бошқа бажарилмайди. Шу туфайли цикл ҳар доим тўхтайди.
Алгоритм ҳар доим рўйхатни яримга бўлади ва биз таҳлилда қандайдир k учун N=2^k-1 деб фараз қилайлик. Агар шундай бўлса, иккинчи ўтишда нечта элемент қолади? Учинчидачи? Умуман олганда, тушунарлики, агар цикл қандайдир ўтишда 2^j-1 элементлт рўйхат билан ишласа, у ҳолда рўйхатнинг биринчи ярмида 2^j-1-1 элемент бўлади, битта элемент ўртада ва 2^j-1-1 элементлар рўйхатнинг иккинчи ярмида бўлади. Шунинг учун кейинги ўтишга 2^j-1-1 элемент қолади (1 < j < k).