Zoeken: lineair en binair zoeken

Om één naam in een gesorteerde lijst van een miljoen te vinden, heeft binair zoeken nooit meer dan 20 controles nodig.

Eén waarde zoeken

Zoeken is bepalen waar een waarde in een verzameling staat of vaststellen dat zij ontbreekt. Je telefoon doet dit wanneer je een contactnaam intypt, een winkel wanneer die controleert of een artikel op voorraad is en een spellingcontrole bij elk woord dat je typt. De invoer is een lijst en een doelwaarde. De uitvoer is de positie van het doel of een teken zoals -1 dat ‘niet gevonden’ betekent.

Lineair zoeken: één tegelijk

De eenvoudigste methode is links beginnen en elke waarde op volgorde controleren totdat je het doel vindt of het einde bereikt. Dit is lineair zoeken. Het werkt op elke lijst, gesorteerd of niet. De kosten hangen af van geluk: staat het doel vooraan, dan is één controle genoeg; staat het achteraan of ontbreekt het, dan controleer je elke waarde. Voor een lijst van n waarden is het slechtste geval n controles. Een tweemaal zo lange lijst kan tweemaal zoveel controles vragen. Daar komt de naam ‘lineair’ vandaan: het werk groeit langs een rechte lijn met de grootte.

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // found it
  }
  return -1;                             // checked everything
}

Binair zoeken: halveer wat overblijft

Als de lijst gesorteerd is, kan het veel beter. Denk aan het getallenraadspel: iemand kiest een getal van 1 tot 100 en antwoordt alleen ‘hoger’ of ‘lager’. Een verstandige speler raadt eerst 50. Wat het antwoord ook is, de helft van de mogelijkheden valt weg. De volgende gok is het midden van wat resteert, enzovoort. Binair zoeken doet precies dit met een gesorteerde lijst. Het houdt twee markeringen, lo en hi, rond het deel waar het doel nog kan staan. Het controleert de middelste waarde. Is dat het doel, dan is het klaar. Is de middelste waarde kleiner, dan is alles links ervan ook kleiner en schuift lo voorbij het midden. Is zij groter, dan schuift hi vóór het midden. Zodra lo hi passeert, resteert niets en staat het doel niet in de lijst.

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // target is to the right
    else hi = mid - 1;                     // target is to the left
  }
  return -1;
}

Hoeveel controles?

Elke controle bij binair zoeken halveert het resterende deel minstens. Begin je met n waarden, dan zijn er na één controle hoogstens ongeveer n/2 over, na twee ongeveer n/4, enzovoort tot er één waarde overblijft. Het aantal halveringen om van n naar 1 te komen is de logaritme van n met grondtal 2, geschreven als log₂ n. Met de laatste controle erbij kost binair zoeken hoogstens ⌊log₂ n⌋ + 1 controles, waarbij ⌊ ⌋ naar beneden afronden betekent. Voor 100 waarden zijn dat 7 controles, en daarom kun je het raadspel altijd in 7 pogingen winnen. Voor 1000 waarden zijn het er 10, voor een miljoen 20 en voor een miljard 30.

De voorwaarde: de lijst moet gesorteerd zijn

Binair zoeken werkt alleen doordat in een gesorteerde lijst één vergelijking vertelt aan welke kant het doel moet staan. In een ongesorteerde lijst vertelt de middelste waarde niets over de buren, dus val je terug op lineair zoeken. Sorteren kost zelf werk (daarover gaan de volgende twee hoofdstukken), dus de keuze hangt af van het gebruik. Zoek je eenmaal in een lijst, dan kan lineair zoeken het goedkoopst zijn. Zoek je duizenden keren in dezelfde lijst, dan loont eenmaal sorteren en daarna binair zoeken snel. Deze afweging tussen gegevens voorbereiden en vragen erover beantwoorden komt overal in het onderwerp terug.