Binary Search vs Linear Search
Linear na paghahanap, na kilala rin bilang ang sequential na paghahanap ay ang pinakasimpleng algorithm ng paghahanap. Naghahanap ito ng isang tinukoy na halaga sa isang listahan sa pamamagitan ng pagsuri sa bawat elemento sa listahan. Ang binary search ay isa ring paraan na ginagamit upang mahanap ang isang tinukoy na halaga sa isang pinagsunod-sunod na listahan. Hinahati ng binary na paraan ng paghahanap ang bilang ng mga elementong nasuri (sa bawat pag-ulit), na binabawasan ang oras na kinuha upang mahanap ang ibinigay na item sa listahan.
Ano ang Linear Search?
Linear na paghahanap ay ang pinakasimpleng paraan ng paghahanap, na sinusuri ang bawat elemento sa isang listahan nang sunud-sunod hanggang sa makakita ito ng tinukoy na elemento. Ang input sa linear na paraan ng paghahanap ay isang sequence (tulad ng array, collection o string) at ang item na kailangang hanapin. Ang output ay totoo kung ang tinukoy na item ay nasa loob ng ibinigay na pagkakasunud-sunod o false kung wala ito sa pagkakasunud-sunod. Dahil sinusuri ng pamamaraang ito ang bawat item sa listahan hanggang sa matagpuan ang tinukoy na item, sa pinakamasamang kaso, dadaan ito sa lahat ng elemento sa listahan bago nito mahanap ang kinakailangang elemento. Ang pagiging kumplikado ng linear na paghahanap ay o(n). Samakatuwid ito ay itinuturing na masyadong mabagal upang magamit kapag naghahanap ng mga elemento sa malalaking listahan. Ngunit ito ay napakasimple at mas madaling ipatupad.
Ano ang Binary Search?
Ang Binary na paghahanap ay isa ring paraan na ginagamit upang mahanap ang isang tinukoy na item sa isang pinagsunod-sunod na listahan. Ang pamamaraang ito ay nagsisimula sa pamamagitan ng paghahambing ng hinanap na elemento sa mga elemento sa gitna ng listahan. Kung ang paghahambing ay nagpasiya na ang dalawang elemento ay pantay ang pamamaraan ay hihinto at ibabalik ang posisyon ng elemento. Kung ang hinanap na elemento ay mas malaki kaysa sa gitnang elemento, sisimulan nitong muli ang pamamaraan gamit lamang ang ibabang kalahati ng pinagsunod-sunod na listahan. Kung ang hinanap na elemento ay mas mababa sa gitnang elemento, sisimulan nitong muli ang pamamaraan gamit lamang ang tuktok na kalahati ng pinagsunod-sunod na listahan. Kung ang hinanap na elemento ay wala sa listahan, ang pamamaraan ay magbabalik ng isang natatanging halaga na nagpapahiwatig na. Samakatuwid ang binary na paraan ng paghahanap ay hinahati ang bilang ng mga elemento na inihambing (sa bawat pag-ulit), depende sa resulta ng paghahambing. Dahil dito, tumatakbo ang binary search sa logarithmic time na nagreresulta sa o(log n) average na performance ng case.
Ano ang pagkakaiba ng Binary Search at Linear Search?
Kahit na ang parehong linear na paghahanap at binary na paghahanap ay mga paraan ng paghahanap, mayroon silang ilang pagkakaiba. Habang ang binary na paghahanap ay gumagana sa mga pinagsunod-sunod na listahan, ang liner na paghahanap ay maaari ding gumana sa mga hindi naayos na listahan. Ang pag-uuri ng isang listahan sa pangkalahatan ay may average na pagiging kumplikado ng kaso ng n log n. Ang linear na paghahanap ay simple at diretsong ipatupad kaysa sa binary na paghahanap. Ngunit, masyadong mabagal ang linear na paghahanap para magamit sa malalaking listahan dahil sa o(n) average na performance ng case nito. Sa kabilang banda, ang binary na paghahanap ay itinuturing na isang mas mahusay na paraan na maaaring magamit sa malalaking listahan. Ngunit ang pagpapatupad ng binary na paghahanap ay maaaring medyo nakakalito at ipinakita ng isang pag-aaral na ang tumpak na code para sa binary na paghahanap ay matatagpuan lamang sa lima sa dalawampung aklat.
