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

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).

Энг ёмон ҳолат таҳлили

Юқорида кўрдикки, рўйхатнинг қолган қисмларида барча ўтишда иккининг даражалари бирга камаяди. Яна циклнинг охирги итерацияси қолган қисм ўлчами 1 га тенг бўлганда бажарилади. Бу эса j = 1 (яъни 2¹-1=1) да бажарилади. Бу шуни кўрсатадики, N=2^k-1 да ўтишлар сони k дан ошмайди. Охирги тенгликдан энг ёмон ҳолда ўтишлар сони га тенглигини топамиз.

Таҳлилда қидириш жараёни учун ечим дарахти ҳам ёрдам бериши мумкин. Ечим дарахти тугунларида мос ўтишда текшириладиган элементлар туради. Етти элементдан иборат рўйхат учун ечим дарахти 2.1-расмда келтирилган. Умумий ҳолда дарахт нибатан баланслаштирилган, яъни биз ҳар доим рўйхат турли қисмларининг ўртасини танлаймиз. Шунинг туфайли солиштиришлар сонини санаш учун 1.3.2 бўлимда бинар дарахтлар учун келтирилган формулалардан фойдаланамиз.

Мадомики биз N=2^k-1 деб фараз қиларканмиз мос келувчи ечим дарахти доим тўлиқ бўлади. Унда k даража, яъни бўлади. Биз ҳар қайси даражада биттадан солиштириш бажаряпмиз, шунинг учун солиштиришлар умумий сони дан ошмайди.



2.1-расм. Етти элементли рўйхатда қидириш учун ечим дарахти