База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / JavaScript

Линейно търсене

Линейното търсене проверява елементите на масив последователно, докато намери съвпадение или достигне края. Не е необходимо масивът да е сортиран; показаната функция връща индекса на първото съвпадение или -1.

Версия: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support

Синтаксис

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

Линейното търсене (linear search) е алгоритъм, а не ключова дума в JavaScript. То проверява елементите последователно, започвайки от индекс 0, и спира при първото съвпадение. Масивът не е необходимо да е сортиран. linearSearch(array, target) връща индекса на съвпадащия елемент или -1, включително за празен масив.

Примерът използва ===: типовете не се преобразуват, затова числото 8 не съвпада с текста "8". NaN не съвпада дори с NaN, а обектите съвпадат само когато са един и същ обект. Функцията не променя масива. Примерът предполага обикновен масив без празни места, който остава непроменен по време на търсенето.

За n елемента най-лошият случай изисква n сравнения: времето е O(n), а допълнителната памет е O(1), ако приемем постоянна цена за четене и сравнение. Незабавно съвпадение отнема O(1) време. Проверявайте резултата с index !== -1, а не с if (index): валидният индекс 0 е falsy, докато -1 е truthy.

Вграденият метод array.indexOf(target) също връща първия индекс при строго сравнение, но пропуска липсващите индексни свойства; показаният цикъл ги прочита и обикновено получава undefined. Алгоритъмът няма собствено издание на ECMAScript; примерът използва синтаксис, наличен в ES3, и не изисква Web APIs или съвременни методи за масиви.

Примери

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));

Резултат

0
3
-1
-1

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници