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
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.