Към съдържанието
wannacode

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

Накратко: Линейното търсене проверява елементите един по един, докато намери търсения или стигне края: O(n) сравнения, и работи с неподреден списък.

Проблем

Скенерът на склада

В склада продуктите са записани в списък в реда, в който са дошли: брашно от понеделник, захар от вторник, олио, ориз. Работникът сканира кутия, а програмата трябва да намери продукта по баркод:

const shelf = [
  { barcode: "3800200101112", name: "Брашно" },
  { barcode: "3800200104403", name: "Захар" },
  { barcode: "3800200107251", name: "Олио" },
  { barcode: "3800200102690", name: "Ориз" },
  { barcode: "3800200109958", name: "Сол" },
  { barcode: "3800200105837", name: "Кафе" },
];

Баркодовете не са подредени. Не можеш да отвориш списъка по средата и да кажеш „оризът е по-нататък“: следващият баркод може да е всякакъв. Как намираш продукта, и колко струва това, когато продуктите са 50 000, а сканиранията 2000 на ден?

Идеята

Поглеждаш всяка кутия

Щом редът не помага, остава едно: започваш от първата кутия и сравняваш баркода ѝ с търсения. Ако съвпада, готово: връщаш мястото. Ако не, минаваш на следващата. Ако кутиите свършат, продуктът го няма.

Това е линейно търсене: минаваш елементите един по един, докато намериш търсения или стигнеш края. Връща се мястото (индексът) или знак за „няма“: -1, защото място -1 няма.

Виж го

Указателят по рафта

function find(shelf, barcode) {
  for (let i = 0; i < shelf.length; i++) {
    if (shelf[i].barcode === barcode) {
      return i;
    }
  }
  return -1;
}
const rice = find(shelf, "3800200102690");
console.log("3800200102690 ->", rice, shelf[rice].name);
console.log("3800200100000 ->", find(shelf, "3800200100000"));
Изход
3800200102690 -> 3 Ориз
3800200100000 -> -1

function find(shelf, barcode) {
  for (let i = 0; i < shelf.length; i++) {
    if (shelf[i].barcode === barcode) {
      return i;
    }
  }
  return -1;
}


const rice = find(shelf, "3800200102690");
const missing = find(shelf, "3800200100000");
Стъпка по стъпка, с думи
  1. Скенерът чете баркода на ориза: 3800200102690. find тръгва от първата кутия.
  2. Сравнява баркода на всяка кутия с търсения: брашно, захар, олио. Не съвпада.
  3. Четвъртата кутия е оризът. return 3: намерен след 4 сравнения.
  4. Баркод, който складът го няма: 3800200100000. find тръгва пак от началото.
  5. Указателят минава всяка кутия и нито една не съвпада.
  6. Кутиите свършиха: return -1 след 6 сравнения. Липсващият продукт е най-лошият случай: n сравнения при n кутии.

Оризът е намерен след 4 сравнения. Липсващият баркод минава всички 6 кутии: само така може да се каже, че го няма.

Пробвай

Попълни

Какво връща find, когато кутиите свършат?

function find(shelf, barcode) {
  for (let i = 0; i < shelf.length; i++) {
    if (shelf[i].barcode === barcode) {
      return i;
    }
  }
  return ;
}

Идеята

Колко сравнения

Броят сравнения зависи от това къде е продуктът:

  • най-добрият случай: първата кутия, 1 сравнение;
  • най-лошият случай: последната кутия или продукт, който го няма, n сравнения;
  • обикновеният случай: ако всяко място е еднакво вероятно, средно около n/2.

Най-лошият и обикновеният случай растат с n, затова линейното търсене е O(n). Програмата брои:

function comparisons(shelf, barcode) {
  let count = 0;
  for (const product of shelf) {
    count++;
    if (product.barcode === barcode) {
      return count;
    }
  }
  return count;
}
console.log("Брашно:", comparisons(shelf, "3800200101112"));
console.log("Ориз:", comparisons(shelf, "3800200102690"));
console.log("Липсващ:", comparisons(shelf, "3800200100000"));
Изход
Брашно: 1
Ориз: 4
Липсващ: 6

Пусни двата крайни случая на голям склад. Броим по едно сравнение на кутия:

  • Баркодът липсва (най-лош случай) O(n)
  • Първият продукт (най-добър случай) O(1)
Алгоритъмn = 10n = 1000n = 100 000
Баркодът липсва (най-лош случай)101000100 000
Първият продукт (най-добър случай)111
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

Първата кутия струва 1 сравнение при всяко n: O(1). Липсващият продукт струва n: при 100 000 продукта са 100 000 сравнения. Паметта е O(1): един индекс.

Пробвай

Предвиди изхода

Солта е петата кутия на рафта. Колко сравнения прави търсенето?

function comparisons(shelf, barcode) {
  let count = 0;
  for (const product of shelf) {
    count++;
    if (product.barcode === barcode) {
      return count;
    }
  }
  return count;
}


console.log("Сол:", comparisons(shelf, "3800200109958"));
Отговор

Виж го

Вградените търсят по същия начин

Всеки език има готово търсене в списък. Отвътре то е същият цикъл:

const barcodes = [
  "3800200101112", "3800200104403", "3800200107251",
  "3800200102690", "3800200109958", "3800200105837",
];
console.log(barcodes.indexOf("3800200102690"));
console.log(barcodes.indexOf("3800200100000"));
console.log(barcodes.includes("3800200102690"));
console.log(shelf.findIndex((p) => p.barcode === "3800200102690"));
Изход
3
-1
true
3
indexOf връща мястото или -1, includes само true или false, а findIndex търси по правило, дадено с функция. Всички минават от първия елемент нататък: O(n).

Едно извикване изглежда като една операция, но вътре са до n сравнения. Вградената функция е по-бърза от твоя цикъл с някакъв постоянен множител, не с порядък.

Пробвай

Намери грешката

Колега е написал търсенето така. Брашното се намира, а оризът „го няма“:

function find(shelf, barcode) {
  for (let i = 0; i < shelf.length; i++) {
    if (shelf[i].barcode === barcode) {
      return i;
    } else {
      return -1;
    }
  }
  return -1;
}
console.log(find(shelf, "3800200101112"));
console.log(find(shelf, "3800200102690"));
Изход
0
-1

На кой ред е грешката?

Избери реда с грешката.

Идеята

Кога е точно на място и кога не

Линейното търсене е точният избор, когато:

  • продуктите са малко: десет или сто сравнения не се усещат;
  • търсиш веднъж: всеки по-бърз начин първо иска поне n стъпки за подготовка;
  • данните са неподредени или се менят постоянно, и няма какво да поддържаш.

Не е, когато търсенията са много. 2000 сканирания на ден в 50 000 продукта са до 100 000 000 сравнения. Тогава подготвяш данните веднъж:

  • таблица баркод → продукт (Map): 50 000 стъпки веднъж, а после всяко търсене е O(1) средно;
  • подреден списък и двоично търсене: подреждането е O(n log n) веднъж, а всяко търсене после е O(log n), около 16 сравнения при 50 000.
const byBarcode = new Map();
for (const product of shelf) {
  byBarcode.set(product.barcode, product);
}
console.log(byBarcode.get("3800200102690").name);
console.log(byBarcode.get("3800200100000"));
Изход
Ориз
undefined

Таблицата струва памет: още n места. Това е същата размяна време срещу памет като set-а в урока „Сложност по памет“.

Упражнение

Всички кутии на един продукт

Реши задачата в редактора си.

Ревизия. Един продукт може да е дошъл с няколко доставки и да е на няколко места в списъка. Напиши findAll(shelf, barcode), която връща всички места на баркода, а не само първото. Рафтът е като горе, плюс още ориз и още сол накрая (места 6 и 7).

Изход
Ориз: 3, 6
Сол: 4, 7

Още задачи

  • Последното място. Върни последното място на баркода. Откъде е по-добре да започнеш?
  • По име, без значение главни и малки. Намери продукта по име („ориз“ и „Ориз“ са същото). Колко сравнения има в най-лошия случай?
  • Продукти под минимума. Изреди всички продукти с наличност под 10 бройки. Може ли да спреш преди края?

Тест

Провери се

1. Списъкът има 10 000 неподредени продукта. Колко сравнения прави линейното търсене за продукт, който го няма?
2. Продуктът е там, а всяко място е еднакво вероятно. Колко сравнения са нужни средно при n продукта?
3. Защо find не връща 0, когато продуктът го няма?
4. Скенерът прави 2000 търсения на ден в 50 000 продукта. Кое е по-добре?
5. Кога линейното търсене е точният избор?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·