De som har prøvd tabeller/matriser i språk som f.eks Java, vet at det ikke er like enkelt og smertefritt å anvende de som i f.eks PHP. I PHP har vi uendelig mange muligheter med matriser og vi kan stort sett gjøre hva vi vil med de, uten å tenke så veldig mye på konsekvensene. Slik er det ikke med høynivåspråk som Java, C++ osv.
Her har vi begrenset muligheter for hva vi kan gjøre og det er enda viktigere at det vi gjør burde være optimalisert og gå så kjapt som mulig. Det er da vi burde se på optimalisering av algoritmene vi gjør i programkodene.
La oss ta et eksempel om en matrise med tall, som ofte er tilfellet. Vi skal søke igjennom matrisen, og finne på hvilken indeks vi har tallet X. For nybegynnere eller late, vil det naturlige valget være en lineær fremgangsmåte. Det vil si vi starter på indeks 0 og går til lengden på tabellen og går igjennom hver eneste indeks og ser om denne passer til argumentet vi har gitt. Denne fremgangsmåten kan være effektiv dersom vi treffer på resultatet på en av de første indeksene og stopper løkken der ved å returnere resultatet. Men hva om vi ikke har et treff før helt i slutten av tabellen? Da ville man ha brukt mye unødvendig tid på å lete igjennom N antall indekser før man traff på den siste. Det må altså være en bedre måte og gjøre dette på.
Ta deg en 5-minutters tenkepause og prøv å tenk ut en bedre fremgangsmåte. Vi har flere måter å bruke en løkke-struktur på. Dersom vi har to nøstede løkker har vi en kvadratisk fremgangsmåte (n²), 3 nøstede løkker så er det n³ osv. Men vi har også noen bedre metoder som er raskere; det er logaritmiske fremgangsmåter. Og binærsøk, som vi skal se på nå, er en såkalt logaritmisk fremgangsmåte.
I steden for å søke igjennom alle indekser, kunne det ikke tenke seg at det er enklere å starte med en sortert tabell og gå til medianen for å så sjekke om medianen er høyere eller lavere enn tallet vi er ute etter? På den måten har vi halvert tabellen vi leter igjennom og har mindre data å lete igjennom. Om man gjør dette igjen, ved å sette medianen av den nye tabellen, og sjekke om den er høyere eller lavere enn tallet vi er ute etter. Sånn fortsetter vi til vi har kommet frem til tallet. Siden det dataen halveres for hver iterasjon er det en logaritimisk fremgangsmåte, og det er lett å se for seg at dette er en mye mer effektiv fremgangsmåte.
La oss se hvordan det blir utført i praksis. Vi starter med en sortert tabell som har verdiene, 2, 3, 6, 9, 12, 21, 24, 31, 33.
Siden den er sortert kan vi se på medianen (som er den midterste verdien) 12. Dersom tallet vi leter etter, 24, er over 12 vet vi at den eksisterer et sted mellom 21 og 33 (siden den ikke er 12), eller fra indeksen 5 til 8. Allerede har vi gått fra en datamengde på 9 tall til bare 4 tall. Dersom vi gjør dette igjen vil medianen bli indeksen 6 (avrundet) og den er hverken over eller under 24, men lik. Derfor har vi indeksen vår, altså 6. Som vi ser er dette en mye mer effektiv måte å lete igjennom en tabell på. Her brukte vi 2 gjennomganger fremfor 6 som ville ha vært nødvendig i en lineær fremgangsmåte.
Nå kan vi se på litt kode som gjør dette for oss. Du kan selv gjøre dette i ditt favorittspråk, men jeg foretrekker per dags dato Java, og vil gjøre det i dette språket.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | public class BinarySearch { public int binarySearch (int[] heystack, int needle) { int low = 0; int high = heystack.length-1; int median; while (low < = high) { median = (high+low)/2; if(needle > heystack[median]) { // Vi skal ha en større verdi, så vi halverer i lengden fra bunnen low = median+1; } else if (needle < heystack[median]) { // Vi skal ha en mindre verdi, så vi halverer i lengden fra toppen high = median-1; } else { // Vi sitter på verdien på medianen som er lik needle, så vi har verdien vår. return median; } } // Vi fant ingenting, derfor returnerer vi -1 return -1; } } |
Dette er en måte å gjøre det på. Vi kan også gå frem på en rekursiv måte dersom vi vil unngå en løkke.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | public class BinarySearch { public int binarySearch (int[] heystack, int needle, int low, int high) { // Vi har gått for langt, og vi har ingen verdi.. if(high < low) return -1; int median = (high+low)/2; if(needle > heystack[median]) { // Vi skal ha en større verdi, så vi halverer i lengden fra bunnen return binarySearch(heystack, needle, median+1, high); } else if (needle < heystack[median]) { // Vi skal ha en mindre verdi, så vi halverer i lengden fra toppen return binarySearch(heystack, needle, low, median-1); } // Vi sitter på verdien på medianen som er lik needle, så vi har verdien vår. return median; } } |
Mange syns kanskje den rekursive metoden er bedre enn den iterasjonsmetoden, men for min del er itereringen like grei.
Håper dette setter litt lys på at det finnes bedre metoder å løse en ting på en den du kanskje tenker først.