Løsningsforslag: Binærsøk¶

Slik virker binærsøk¶

Trykk deg gjennom steg for steg. Se hvordan low, mid og high flytter seg, og hvordan halve lista forsvinner for hvert gjett.

Pseudokode¶

Før vi skriver kode, er det lurt å beskrive framgangsmåten i vanlig språk. low og high markerer den delen av lista vi fortsatt leter i. mid er plassen midt imellom, og det er den vi sjekker. For hver runde flytter vi enten low eller high inn mot midten. Da blir det halvparten så mye igjen å lete i.

Under ser du det samme på to måter. Velg den du synes er lettest å følge.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

START
low = 0
high = lengde(arr) - 1

SÅ LENGE low <= high
    mid = (low + high) / 2 (avrundet ned)

    HVIS arr[mid] == target
        RETURNER mid
    ELLERS HVIS arr[mid] < target
        low = mid + 1
    ELLERS
        high = mid - 1

RETURNER -1
SLUTT

flowchart TD
    A([Start med hele lista]) --> C{Noe igjen å lete i?}
    C -- Ja --> D[Sjekk tallet i midten]
    D --> E{Fant vi tallet?}
    E -- Ja --> F([Ferdig! Svaret er plassen til tallet])
    E -- Nei --> I[Behold halvdelen der tallet kan ligge]
    I --> C
    C -- Nei --> H([Tallet finnes ikke. Svaret er -1])

Ferdig kode¶

Her er pseudokoden oversatt til ekte kode. Framgangsmåten er helt lik i alle tre språkene. Det er bare skrivemåten (syntaksen) som er forskjellig.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);

    console.log(`low=${low} mid=${mid} high=${high} arr[mid]=${arr[mid]}`);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1; // ikke funnet
}

if (typeof module !== "undefined") module.exports = binarySearch;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        print(f"low={low} mid={mid} high={high} arr[mid]={arr[mid]}")

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # ikke funnet

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

<?php
function binarySearch(array $arr, int $target): int {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $mid = intdiv($low + $high, 2);

        echo "low=$low mid=$mid high=$high arr[mid]={$arr[$mid]}\n";

        if ($arr[$mid] === $target) {
            return $mid;
        } elseif ($arr[$mid] < $target) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }

    return -1; // ikke funnet
}

Forklaring¶

low, high og mid¶

Hvert tall i lista står på en bestemt plass. Plassen kalles en indeks. Den første plassen har indeks 0, ikke 1.

low og high holder styr på hvor vi fortsatt leter. low er den første plassen i søkeområdet, og high er den siste. I starten dekker de hele lista.

mid er plassen midt imellom, og det er den vi sjekker hver runde. Regnestykket (low + high) / 2 kan gi et desimaltall, for eksempel 3,5. Men det finnes ingen plass 3,5 i en liste, så vi runder alltid ned. Da blir svaret 3.

De tre mulighetene¶

target er tallet vi leter etter, og arr[mid] er tallet som står på plassen vi sjekker. Når vi sammenligner de to, finnes det bare tre muligheter:

Det er de to siste radene som gjør binærsøk raskt. Fordi lista er sortert, vet vi hvilken vei tallet ligger. Da kan vi hoppe over hele den andre halvdelen, og løkken går videre med bare det som er igjen.

Figuren under viser ett slikt hopp. Vi leter etter tallet 40:

Når søket stopper¶

Løkken går så lenge low <= high, altså så lenge det er noe igjen å lete i. Når low blir større enn high, har de passert hverandre. Da er det ingen plasser igjen å sjekke, og tallet finnes ikke i lista.

Da returnerer vi -1. Plassene i en liste er alltid 0 eller høyere, så -1 kan aldri være en ekte plass. Får du -1 tilbake, betyr det "ikke funnet".