Бінарны пошук - адзін з самых простых спосабаў знаходжання элемента ў масіве

Даволі часта праграмісты, нават пачаткоўцы, сутыкаюцца з тым, што ёсць набор лікаў, у якім неабходна знайсці пэўную колькасць. Вось гэтую калекцыю называюць масівам. А каб знайсці патрэбны элемент у ім, ёсць велізарнае мноства спосабаў. Але самым простым сярод іх па праве можна лічыць бінарны пошук. У чым жа заключаецца дадзены метад? І як рэалізаваць бінарны пошук? Паскаль з'яўляецца самай простай асяроддзем для арганізацыі такой праграмы, таму будзем выкарыстоўваць менавіта яго для вывучэння.

Спачатку разбяром, у чым перавагі гэтага метаду, бо так мы зможам зразумець, які сэнс у вывучэнні дадзенай тэмы. Такім чынам, выкажам здагадку, ёсць масіў з памерам хоць бы 100000000 элементаў, у якім трэба знайсці пэўны. Вядома, гэтую задачу лёгка можна вырашыць простым лінейным пошукам, пры якім мы з дапамогай цыкла будзем параўноўваць шуканы элемент з усімі тымі, што ёсць у масіве. Праблема ў тым, што рэалізацыя гэтай ідэі будзе займаць занадта шмат часу. У простай паскалевской праграме на некалькі працэдур і з трыма радкамі асноўнага тэксту вы гэтага не заўважыце, але калі прыступіце да больш-менш буйных праектах з вялікай колькасцю разгалінаванняў і нядрэнным функцыяналам, гатовая праграма будзе грузіцца занадта доўга. Асабліва ў тым выпадку, калі ў кампутара будзе слабая працаздольнасць. Таму і існуе бінарны пошук, які скарачае час пошуку як мінімум удвая.

Такім чынам, у чым жа заключаецца прынцып працы дадзенага метаду? Адразу варта сказаць, што працуе бінарны пошук не ў любым масіве, а толькі ў адсартаваным наборы лікаў. На кожным наступным кроку бярэцца сярэдні элемент масіва (маецца на ўвазе па нумары элемента). Калі шуканае лік больш сярэдняга, значыць усё тое, што знаходзіцца злева, гэта значыць менш сярэдняга элемента, можна адкінуць і не шукаць там. І наадварот, калі менш за сярэдні - сярод тых лікаў, што справа, можна не шукаць. Далей абярэм новую вобласць пошуку, дзе першым элементам стане сярэдні элемент ўсяго масіва, а апошні так і застанецца апошнім. Сярэднім жа лікам новай вобласці стане ¼ ўсяго адрэзка, то ёсць (апошні элемент + сярэдні элемент ўсяго масіва) / 2. Зноў вырабляецца тая ж аперацыя - параўнанне з сярэднім лікам масіва. Калі шуканая велічыня менш за сярэдні, адкідаем правую частку, і гэтак жа робім далей, пакуль вось гэты сярэдні элемент не апынецца шуканым.

Вядома, лепш за ўсё паглядзець на прыкладзе, як пішацца бінарны пошук. Pascal тут падыдзе любы - версія не важная. Напішам простую праграму.

У ёй будзе масіў ад 1 да h пад назвай "massiv", пераменная, якая пазначае ніжнюю мяжу пошуку, названая "niz", верхняя мяжа, названая "verh", сярэдні элемент пошуку - "sredn"; і шуканае лік - "isk".

Такім чынам, спачатку прызначаем верхнюю і ніжнюю мяжы інтэрвалу пошуку:

niz: = 1;
verh: = h + 1;

Затым арганізоўваем цыкл "пакуль ніжняя менш верхняй мяжы":

While niz begin

На кожным кроку дзелім адрэзак на 2:

sredn: = (niz + verh) div 2; {Выкарыстоўваем функцыю div, таму што дзелім без астатку}

Кожны раз праводзім праверку. Калі сярэдні роўны шуканага, перарываем цыкл, так як патрэбны элемент ўжо знойдзены:

іf sredn = isk then break;

Калі сярэдні элемент масіва больш шуканага, адкідаем левую частку, гэта значыць верхняй мяжой прызначаем сярэдні элемент:

if massiv [sredn]> isk then verh: = sredn;

А калі наадварот, то яго робім ніжняй мяжой:

else niz: = sredn;
end;

Вось і ўсё, што будзе ў праграме.

Разбяром, як будзе выглядаць бінарны метад на практыцы. Возьмем такі масіў: 1, 3, 5, 7, 10, 12, 18 і будзем шукаць у ім лік 12.

Усяго ў нас 7 элементаў, таму сярэднім будзем чацвёрты, яго значэнне 7.

Так як 12 больш 7, элементы 1,3 і 5 мы можам адкінуць. Далей у нас засталося 4-га, 4/2 без астатку роўна 2. Значыць, новым сярэднім элементам будзе 10.

Так як 12 больш 10, адкідаем 7. Застаецца толькі 10, 12 і 18.

Тут сярэдні элемент ўжо 12, гэта і ёсць шуканае лік. Задача выкананая - лік 12 знойдзена.