binærsøk

Binærsøk er en effektiv søkealgoritme brukt til å finne et bestemt element i en sortert samling. Den utnytter at elementene er ordnet ved å halvere søkeområdet i hver iterasjon, noe som gir rask ytelse på store datasett. Algoritmen kan implementeres både rekursivt og iterativt; den iterative versjonen er vanligst på grunn av lavere minnebruk.

Tilnærmingen starter med to indeksvariabler som avgrenser området: lo (venstre) = 0 og hi (høyre) = n−1. Mens lo ≤ hi gjør man beregningen mid = floor((lo + hi) / 2). Sammenlign deretter a[mid] med målverdien x. Hvis a[mid] er lik x, har man funnet elementet. Hvis a[mid] < x, søket fortsetter i den høyre halvdelen ved å sette lo = mid + 1. Ellers fortsetter søket i den venstre halvdelen ved å sette hi = mid − 1.

Kompleksitet: Tiden det tar i verste fall er O(log n), fordi søkeområdet halveres i hver iterasjon. Minnebruken for den iterativ versjonen er konstant, mens en rekursiv implementasjon krever O(log n) ekstra plass på stakken.

Bruksområder: Binærsøk brukes ofte til oppslag i store sorterte lister og som byggesten i datastrukturer for oppslagsoperasjoner med medlemskap. Det kan også anvendes til å finne første eller siste posisjon av et mål når duplikater finnes ved hjelp av varianter som lower_bound og upper_bound.

Vilkår og hensyn: Dataene må være sortert før binærsøk kan anvendes. Ved duplikater vil standard binærsøk finne en tilfeldig forekomst; spesialiserte varianter kan returnere første eller siste posisjon. Ved inkonsistente eller usorterte datastrukturer er binærsøk ineffektivt uten forberedende sortering.