Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. Algorithms
Code

Ang Binary Search Algorithm sa JavaScript

by
Difficulty:IntermediateLength:MediumLanguages:

Tagalog (Wikang Tagalog) translation by Anna Nelson (you can also view the original English article)

Final product image
Ano ang Inyong Lilikhain 

Sa post na ito, ikukumpara ko ang linear search at binary search algorithm. Makikita mo ang pseudocode sa bawat algorithm, kasama ang mga halimbawa at hakbang-hakbang na gabay sa paggamit ng bawat isa.

Pagsisimula

Bilang isang programmer, nais mong makahanap ng pinakamagandang solusyon sa problema upang ang iyong code ay hindi lamang tama kung hindi mahusay rin. Ang pagpili ng isang suboptimal algorithm ay maaaring mangahulugan ng mas mahabang oras ng pagkumpleto, mas maraming pagkakumplikado ng code, o ang mas masama pa ay ang pagkasira ng program. Maaaring ginamit mo na ang search algorithm upang maghanap ng mga bagay sa isang koleksyon ng datos. Ang JavaScript language ay may iba’t-ibang pamamaraan,  tulad ng find, upang maghanap ng mga bagay nang maayos. Subalit, ang mga pamamaraan na ito ay gumagamit ng linear search. Ang linear search algorithm ay nagsisimula sa unahan ng listahan at ikinukumpara ang bawat elemento gamit ang search value hanggang sa ito ay makita. Ito ay maganda kung ikaw ay may mababang bilang ng mga elemento. Ngunit kung ikaw ay naghahanap sa malalaking listahan na may libu-libo o milyun-milyong elemento, kinakailangan mo ng mas magandang paraan upang maghanap ng mga bagay. Dito mo gagamitin ang binary search. Sa tutoryal na ito, ipapaliwanag ko kung paano ginagamit ang binary search at kung paano gagamitin ang algorithm sa JavaScript. Una, susuriin natin ang linear search algorithm.

Ang Linear Search

Magsisimula tayo sa pagpapaliwanag kung paano gagamitin ang linear search sa JaveScript. Gagawa tayo ng function na tinatatawag na linearSearch na tumatanggap ng value ng isang integer o string at ng array bilang mga parameter. Ang function ay maghahanap ng bawat elemento sa array para sa value at ibabalik ang posisyon ng value sa array kung ito ay makita. Kung ang value ay wala sa array, ito ay babalik na -1. Halimbawa, ang pagtawag ng linearSearch(1, [3, 4, 2, 1, 5]) ay magbabalik ng 3 at ang pagtawag ng linearSearch(0, [3, 4, 2, 1, 5]) ay magbabalik ng -1.

Ito ang ilan sa mga pseudocode para sa ating function:

Ang Implementasyon ng JavaScript sa Linear Search

Ito ang implementasyon ng JavaScript ng linear search algorithm:

Mahalagang malaman na ang linear search algorithm ay hindi na nangangailangang gumamit ng pinagsunod-sunod na listahan. At ang algorithm ay maaaring i-customize para magamit sa iba’t-ibang sitwasyon tulad ng paghahanap ng array ng mga bagay gamit ang key. Kung ikaw ay may array ng datos ng customer na may kasamang mga key para sa pangalan at apelyido, maaari mong subukan kung ang array ay may tinukoy na pangalan ng customer. Sa kasong ito, sa halip na suriin kung ang list[index] ay katumbas ng ating search value, susuriin mo muna ang list[index].first.

Sa halimbawa sa itaas, ginamit ko ang linearSearch function sa array na may 5 elemento. Sa pinakamasamang kaso, kung ang search value ay wala sa listahan o kung nasa hulihan ng listahan, ang function ay kinakailangang gumawa ng 5 paghahambing. Dahil ang ating array ay napakaliit, hindi na natin kailangan pang mag-optimize sa pamamagitan ng paggamit ng ibang algorithm. Subalit, hanggang sa tiyak na punto, hindi na tama pang gumamit ng linear search algorithm at dito mas kinakailangang gumamit ng isang binary search algorithm. 

Ang Binary Search

Isipin mo kung ikaw ay naglalaro ng isang number guessing game. Ikaw ay hihilinging manghula ng numero sa pagitan 1 at 100. Kung ang iyong numero ay napakataas o napakababa, ikaw ay makakakuha ng pahiwatig. Ano ang iyong magiging estratehiya? Ikaw ba pipili lamang ng mga numero basta-basta? Ikaw ba ay magsisimula sa 1, pagkatapos 2, at iba pa hanggang sa mahulaan nang tama? Kahit na ikaw ay may walang katapusang pagkakataon na manghula gusto mong tumama ang hula mo sa ilang pagsubok lamang kung possible. Kaya, maaaring magsimula kang manghula sa 50. Kung ang iyong numero ay mas mataas, maaaring huhulaan mo ang 75. Kung mas mababa, ibig sabihin ang numero ay nasa pagitan ng 50 at 75 at pipili ka ng numero sa gitna. Ikaw ay magpapatuloy hanggang sa mahulaan mo ang tamang numero. Ito ay katulad ng binary search.

Hindi tulad ng linear search, ang binary search ay gumagamit ng pinagsunod-sunod na listahan. Upang maghanap ng value, ikukumpara mo muna ang value sa gitnang elemento ng listahan. Kung ito ay magkatumbas, nahanap mo na ang search value. Kung ang search value ay mas mataas sa gitnang elemento, hinanap mo ang nasa itaas na kalahati ng datos. Pagkatapos ikukumpara mo ang gitnang elemento ng seksyon na ito sa search value. Bilang kahalili, kung ang item ay mas mababa sa gitnang elemento, nahanap mo ang nasa ibabang kalahati ng listahan at ikinumpara ang gitnang value. Ang listahan ay paulit-ulit na hinati sa kalahati hanggang sa makita ang elemeto o kung wala ng mga bagay na hahanapin.

Para mahanap ang 9 sa listahan:

Una kailangan nating hanapin ang gitnang elemento. Ito ang element sa posisyon Math.floor((first + last)/2) na kung saan ang first ay ang unang index, at ang last ay ang huling index. Pinili namin na ibaba sa pinakamalapit na numero para kung sakaling ang resulta ay isang praksyon ito ay magiging isang buong numero. Ang gitnang elemento sa listahan na ito ay 5. Ang search value 9 natin ay mas mataas sa 5 kaya maghahanap tayo sa listahan:

Ang gitnang elemento ng bahaging ito ay 8. Ang siyam ay mas malaki sa 8 kaya maghahanap tayo sa listahan:

Ang gitnang element ay 9, kaya pwede na nating itigil ang paghahanap dito.

Narito ang ilang pseudo code na nagpapakita ng algorithm sa itaas para sa binary search:

Ang Implementasyon ng JavaScript sa Binary Search

Ngayon lagyan natin ng code ang binary search algorithm sa JavaScript!

Tayo ay gagawa ng isang function, binarySearch, na tumatanggap ng isang value at array bilang parameters. Ito ay magbabalik ng index kung saan ang value ay nagaganap sa listahan kung makita. Kung ang value ay hindi makita ito ay babalik ng -1. Ito ang aming implementasyon na isinulat sa JavaScript:

Konklusyon

Sa tutoryal na iyo, nakita natin kung paano gawin ang algorithm ng linear search at a binary search. Mas simple ang linear search algorithm at hindi nangangailangan ng isang sorted array. Subalit, hindi ito epektibo  na gamitin sa mas malaking array. Sa pinakamasamang kaso, kinakailangang maghanap ng algorithm ng lahat ng elemento na gagamit ng n comparison (na kung saan ang n ay ang numero ng elemento).

Ang binary search algorithm, sa kabilang banda, ay nangangailangan na isaayos muna ang array at mas kumplikado na gamitin. Subalit, ito ay mas magandang gamitin kung isaalang-alang mo ang halaga ng sorting. Halimbawa, ang array na may 10 elemento ay magkakaroon ng hanggang 4 na paghahambing sa isang binary search laban sa 10 para sa isang linear search – hindi tulad ng isang malaking pagbabago. Subalit, para sa array na may 1,000,000 elemento ang pinakamasamang kaso sa binary search ay may 20 paghahambing lamang. Ito ay napakalaking pagbabago sa linear search!

Ang kaalaman sa paggamit ng binary search ay hindi lamang pagsasanay para sa isang tanong sa pakikipanayam. Ito ay isang praktikal na kasanayan na maaaring mas magpaganda ng iyong code. 

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.