KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / JavaScript

Lineair zoeken

Lineair zoeken controleert array-elementen op volgorde totdat het een overeenkomst vindt of het einde bereikt. Sorteren is niet nodig; de getoonde functie geeft de index van de eerste overeenkomst terug, of -1.

Versie: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support

Syntax

function linearSearch(array, target) {
  for (var i = 0; i < array.length; i++) {
    if (array[i] === target) return i;
  }
  return -1;
}

Lineair zoeken (linear search) is een algoritme, geen JavaScript-trefwoord. Het controleert elementen achtereenvolgens vanaf index 0 en stopt bij de eerste overeenkomst. De array hoeft niet gesorteerd te zijn. linearSearch(array, target) geeft de index van het overeenkomende element terug, of -1, ook bij een lege array.

Het voorbeeld gebruikt ===: typen worden niet omgezet, dus het getal 8 komt niet overeen met de tekst "8". NaN komt zelfs niet overeen met NaN, en objecten komen alleen overeen als het hetzelfde object is. De functie wijzigt de array niet. Het voorbeeld gaat uit van een gewone array zonder gaten die tijdens het zoeken onveranderd blijft.

Voor n elementen zijn in het slechtste geval n vergelijkingen nodig: de tijd is O(n) en het extra geheugengebruik O(1), ervan uitgaande dat lezen en vergelijken een constante kost hebben. Een directe overeenkomst kost O(1) tijd. Controleer het resultaat met index !== -1, niet met if (index): de geldige index 0 is falsy, terwijl -1 truthy is.

De ingebouwde methode array.indexOf(target) geeft met strikte vergelijking ook de eerste index terug, maar slaat ontbrekende indexeigenschappen over; de getoonde lus leest ze en krijgt meestal undefined. Het algoritme hoort niet bij een specifieke ECMAScript-editie; het voorbeeld gebruikt syntax die beschikbaar is in ES3 en heeft geen Web APIs of moderne arraymethoden nodig.

Voorbeelden

function linearSearch(array, target) {
  for (var i = 0; i < array.length; i++) {
    if (array[i] === target) return i;
  }
  return -1;
}

var values = [8, 3, 8, 5];
console.log(linearSearch(values, 8));
console.log(linearSearch(values, 5));
console.log(linearSearch(values, 9));
console.log(linearSearch([], 8));

Resultaat

0
3
-1
-1

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen