Klassisk binær søgning: venstre, højre, midt

Binær søgning reducerer en lineær gennemgang med O(n) til O(log n) ved at halvere søgerummet i hvert trin. I et array med en million elementer kræver en lineær gennemgang op til 1.000.000 sammenligninger, mens binær søgning højst kræver 20. Denne effektivitet gør den til en af de algoritmer, der oftest testes ved programmeringsjobsamtaler.

Den centrale pointe er, at et sorteret array efter én enkelt sammenligning lader dig afgøre, hvilken halvdel af de resterende data du helt kan forkaste.

Binær søgning bruger tre indeksmarkører: lo (venstre grænse), hi (højre grænse) og mid (midtpunkt). Ved hver iteration beregner du mid = (lo + hi) // 2 og sammenligner søgeværdien med arr[mid]. Hvis søgeværdien er mindre, flytter du hi = mid - 1; hvis den er større, flytter du lo = mid + 1; hvis de er ens, har du fundet den.

Løkken fortsætter, så længe lo <= hi. Når løkken afsluttes uden at finde søgeværdien, returnerer du -1.

Udtrykket mid = (lo + hi) // 2 kan medføre heltalsoverløb i sprog med heltal med fast bredde (Java, C++). Pythons heltal har vilkårlig præcision, så der opstår aldrig overløb, men til en jobsamtale forventes det stadig, at du kender det sikre alternativ: mid = lo + (hi - lo) // 2.

Denne form beregner det samme midtpunkt, men lægger kun halvdelen af afstanden til lo til i stedet for først at lægge begge grænser sammen. Hvis du nævner dette til en jobsamtale, viser det, at du er opmærksom på lavniveauhensyn.

En af de vanskeligste dele ved binær søgning er at vælge, om hi peger på det sidste gyldige indeks (inklusiv, hi = len(arr) - 1) eller på pladsen lige efter slutningen (eksklusiv, hi = len(arr)). Forskellige konventioner kræver forskellige løkkebetingelser og opdateringer af grænserne.

Med inklusive grænser skal du bruge while lo <= hi og opdatere hi = mid - 1. Med eksklusive grænser skal du bruge while lo < hi og opdatere hi = mid. At blande konventionerne er den mest almindelige årsag til fejl i implementeringer af binær søgning.

Binær søgning kan skrives rekursivt ved at sende opdaterede grænser for lo og hi gennem kaldestakken. Hvert rekursivt kald halverer søgerummet, så dybden er O(log n). Basistilfældet opstår, når lo > hi (ikke fundet), eller når arr[mid] == target (fundet).

Den iterative version foretrækkes i produktionskode, fordi den undgår ekstra omkostninger til stakrammer, men den rekursive version tydeliggør divide-and-conquer-strukturen bedre på en tavle.

Robust binær søgning skal kunne håndtere kanttilfælde uden at gå ned. De tre mest almindelige er: et tomt array (løkken udføres aldrig, og -1 returneres korrekt), et array med ét element (mid er lig med lo og hi, så én sammenligning er nok) og søgeværdier uden for området (lo kommer til sidst til at overstige hi, og -1 returneres).

Afprøv altid din implementering med disse inputværdier, før du går videre til opfølgende spørgsmål i en jobsamtale.

Binær søgning har tidskompleksiteten O(log n), fordi hver sammenligning halverer søgerummet. Efter k sammenligninger er det resterende søgerum n/2^k; søgningen slutter, når dette når 1, så k = log₂ n.

Pladskompleksiteten er O(1) for den iterative version (kun tre heltalsvariabler) og O(log n) for den rekursive version på grund af kaldestakkens dybde. Angiv altid begge dele til en jobsamtale, og foretræk den iterative form, når pladsen er begrænset.

Klassisk binær søgning returnerer et vilkårligt indeks, hvor søgeværdien findes. Men mange interviewopgaver beder om den første eller sidste forekomst af en søgeværdi. I de tilfælde skal du fortsætte søgningen, selv efter at du har fundet et match — i stedet for at returnere med det samme skal du indsnævre grænsen og fortsætte.

Når du søger efter den første forekomst, skal du efter at have fundet arr[mid] == target gemme mid som en kandidat og sætte hi = mid - 1. For den sidste forekomst skal du sætte lo = mid + 1.

Pythons standardbibliotek indeholder bisect.bisect_left(arr, x) og bisect.bisect_right(arr, x) til binær søgning, der er klar til brug i produktion. bisect_left returnerer det venstre indeks, hvor x kan indsættes, så arrayet forbliver sorteret, hvilket i praksis finder den første position, hvor arr[i] >= x.

Det kan være tilladt at bruge bisect til en jobsamtale; spørg altid først. Det er stadig afgørende at vide, hvordan modulet fungerer bag kulisserne (det er binær søgning med O(log n)).

Tre fejl står for de fleste fejl i binær søgning til jobsamtaler. For det første en forkert løkkebetingelse: Hvis du bruger < i stedet for <= med inklusive grænser, springer du det sidste resterende element over. For det andet en forkert opdatering af grænsen: Hvis du glemmer +1 eller -1, opstår der en uendelig løkke, når lo == hi. For det tredje at arbejde på et usorteret array: Binær søgning er kun korrekt på sorterede data.

Sig følgende højt, før du skriver binær søgning: 'Arrayet er sorteret, mine grænser er inklusive, og min løkke kører, så længe lo <= hi.'

Når du ser et problem med et sorteret array, en monotont voksende funktion eller et søgerum, der kan halveres, bør du straks overveje binær søgning. Forklar din tankegang til en jobsamtale: 'Fordi arrayet er sorteret, kan jeg forkaste halvdelen af elementerne ved hver sammenligning, hvilket giver O(log n).'

Afprøv altid din løsning med mindst tre inputværdier: en værdi i begyndelsen, en værdi i slutningen og en værdi, der ikke findes. Hvis du på eget initiativ angiver kompleksiteten — 'tid O(log n), plads O(1)' — før du bliver spurgt, viser det et stærkt grundlag.

I denne lektion lærte du: binær søgning halverer søgerummet ved hvert trin og giver tidskompleksiteten O(log n), den inklusive grænsekonvention bruger lo <= hi med opdateringerne lo = mid+1 og hi = mid-1, og for at finde den første eller sidste forekomst fortsætter du søgningen efter et match i stedet for at returnere med det samme. Næste gang undersøger vi, hvordan binær søgning udvides til roterede og usorterede arrays.