Двоично търсене в JavaScript

Проблем

Филтърът, който чете целия каталог

Магазинът има 1 000 000 продукта, а ценоразписът е подреден по цена. Филтърът „точна цена“ търси с цикъл от началото, като линейното търсене. Цените в кода са в евроцентове: от 2 до 2 000 000. Клиент търси продукт за 20 000,01 €, а такъв няма:

const n = 1_000_000;
const prices = Array.from({ length: n }, (_, i) => 2 * (i + 1));
const target = 2 * n + 1;

let comparisons = 0;
let found = -1;
for (let i = 0; i < n; i++) {
  comparisons++;
  if (prices[i] === target) {
    found = i;
    break;
  }
}
console.log(`Индекс: ${found}`);
console.log(`Сравнения: ${comparisons}`);

Индекс: -1
Сравнения: 1000000

Милион сравнения, за да кажеш „няма“. А при всяко отваряне на страницата филтърът се пуска за десетки цени.

Цените са подредени, а цикълът не се възползва от това. Когато търсиш дума в речник, не четеш от първата страница. Отваряш по средата и гледаш дали думата е преди или след.

Идеята

Питай средата, изхвърли половината

Погледни цената по средата на ценоразписа:

ако е търсената, готово;
ако е по-малка, търсената може да е само вдясно. Лявата половина отпада, заедно със средата;
ако е по-голяма, търсената може да е само вляво.

После същото с половината, която остава. Това е двоично търсене (binary search). Обхватът, в който цената още може да е, се пази с два индекса: lo (началото) и hi (краят). Средата е mid.

Всяко сравнение разполовява обхвата. 1 000 000 цени стават 500 000, после 250 000, и след около 20 деления остава една. Колко пъти делиш на 2, докато стигнеш до 1, се казва логаритъм при основа 2: log₂ 1 000 000 ≈ 20. Затова двоичното търсене е O(log n), а линейното е O(n).

Условието е едно: масивът трябва да е подреден. В неподреден масив „по-малка е, значи е вдясно“ не е вярно.

Виж го

lo, mid и hi в ценоразписа

function find(prices, target) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (prices[mid] === target) {
      return mid;
    } else if (prices[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

const prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58];
console.log(`Индекс: ${find(prices, 49)}`);

Индекс: 12

function find(prices, target) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (prices[mid] === target) {
      return mid;
    } else if (prices[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

Стъпка по стъпка, с думи

Ценоразписът е подреден: 15 цени. Търсим 49 €. lo и hi обхващат всичко, от 0 до 14.
mid = 7: 27 € < 49 €, значи цената е вдясно. lo = 8, лявата част отпада. Остават 7 цени.
mid = 11: 44 € < 49 €, значи цената е вдясно. lo = 12, лявата част отпада. Остават 3 цени.
mid = 13: 53 € > 49 €, значи цената е вляво. hi = 12, дясната част отпада. Остава 1 цена.
mid = 12: 49 €. Това е търсената цена: find връща 12.
4 сравнения. Търсене от началото би погледнало 13 цени, а за 1 000 000 цени двоичното търсене иска най-много 20.

Средата е Math.floor((lo + hi) / 2): делението в JavaScript дава дробно число, а индексът трябва да е цял. В Java и C# се пише по друг начин, защото там сборът може да прелее. На една от следващите карти е как е в JavaScript.

По-точно, за любопитните

Най-лошият случай е, когато цената я няма: обхватът се дели, докато lo не мине hi. За n цени това са най-много ⌊log₂ n⌋ + 1 сравнения: 4 за 10 цени, 10 за 1000, 20 за 1 000 000. Най-добрият случай е едно сравнение: цената е точно на средата.

Тук „сравнение“ е една проба на mid. Проверката за равно и за по-малко са два реда в кода, но питат за една и съща цена.

Пробвай

Предвиди колко проби

Подредени цени в евроцентове: 2, 4, 6, …, 2000. Търси се 2001, а такава цена няма. Колко пъти минава цикълът?

const n = 1000;
const prices = Array.from({ length: n }, (_, i) => 2 * (i + 1));
const target = 2 * n + 1;

let steps = 0;
let lo = 0;
let hi = n - 1;
while (lo <= hi) {
  const mid = Math.floor((lo + hi) / 2);
  steps++;
  if (prices[mid] === target) {
    break;
  } else if (prices[mid] < target) {
    lo = mid + 1;
  } else {
    hi = mid - 1;
  }
}
console.log(steps);

Отговор

Пробвай

Попълни

Цената на mid е по-малка от търсената. Откъде започва новият обхват?

function find(prices, target) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (prices[mid] === target) {
      return mid;
    } else if (prices[mid] < target) {
      lo = ;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

Идеята

Границите: къде греши всеки

Двоичното търсене се пише в шест реда, а е известно с това, че се пише грешно. Грешката почти винаги е с едно: < вместо <=, mid вместо mid - 1. Казва се off-by-one (грешка с единица).

Пазиш я с едно решение: какво значат lo и hi, и после го спазваш навсякъде.

Затворен обхват [lo, hi]: и двата края може да са цената. hi започва от последния индекс, цикълът е докато lo <= hi, а изхвърлената среда е hi = mid - 1 и lo = mid + 1. Това е find от горе.
Полуотворен обхват [lo, hi): hi е първото място след обхвата. hi започва от дължината на масива, цикълът е докато lo < hi, а наляво се отива с hi = mid, защото hi така и така не е в обхвата.

Двете са верни. Грешката е, когато ги смесиш. Ето затворен обхват с hi = mid от полуотворения. Търси се 4 €, а такава цена няма. Ограничителят спира цикъла след 8 проби, иначе нямаше да спре:

function find(prices, target) {
  let lo = 0;
  let hi = prices.length - 1;
  let probes = 0;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    console.log(`lo=${lo} hi=${hi} mid=${mid}`);
    if (++probes === 8) {
      console.log("Спирам след 8 проби: lo и hi не мърдат");
      return -1;
    }
    if (prices[mid] === target) {
      return mid;
    } else if (prices[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return -1;
}

const prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58];
find(prices, 4);

lo=0 hi=14 mid=7
lo=0 hi=7 mid=3
lo=0 hi=3 mid=1
lo=0 hi=1 mid=0
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
Спирам след 8 проби: lo и hi не мърдат

Когато lo и hi станат 1, средата е 1, цената там е 5 €, повече от 4 €, и hi = mid пак е 1. Нищо не се сменя. Това е безкраен цикъл: програмата не пада, само виси.

Пробвай

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

Търсенето намира 49 €, но не намира най-скъпия продукт, 58 €, макар че той е в ценоразписа:

const prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58];
console.log(`Индекс: ${find(prices, 58)}`);

Индекс: -1

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

Идеята

Когато (lo + hi) / 2 прелива

В Java и C# int стига до 2 147 483 647, и при масив с повече от милиард елемента (lo + hi) / 2 прелива: сборът става отрицателно число. Затова там средата се пише lo + (hi - lo) / 2.

В JavaScript числата са с плаваща запетая и са точни до 2⁵³, затова lo + hi не прелива. Капанът е другаде, в краткия запис със >>:

const lo = 1_500_000_000;
const hi = 2_000_000_000;
console.log(Math.floor((lo + hi) / 2));
console.log((lo + hi) >> 1);
console.log((lo + hi) >>> 1);

1750000000
-397483648
1750000000

>> 1 първо превръща числото в 32-битово цяло със знак, а 3 500 000 000 не се побира в него. >>> 1 го превръща в 32-битово без знак, затова дава вярната среда. Масив в JavaScript има най-много 2³² − 1 елемента. Math.floor((lo + hi) / 2) е вярно винаги.

По-точно, за любопитните

Грешката не е измислена. Двоичното търсене в стандартната библиотека на Java, Arrays.binarySearch, е имало (low + high) / 2 девет години. Джошуа Блох го описва през 2006 г. в статията „Nearly All Binary Searches and Mergesorts are Broken“: програма с масив от повече от 2³⁰ елемента пада с ArrayIndexOutOfBoundsException. Днес там пише (low + high) >>> 1.

Виж го

Първата цена от 20 € нагоре

Филтърът „цена от 20 €“ не търси точна цена. Търси първото място, където цената е поне 20 €: от него нататък са всички продукти, които трябва да покаже. Това се казва долна граница (lower bound). Тя е и първото срещане: ако цените имат три продукта по 15 €, долната граница на 15 е първият от тях.

find не я дава: той спира на първото 15, на което стъпи. Долната граница е с полуотворен обхват, и цикълът не спира при равно, а продължава наляво:

function lowerBound(prices, target) {
  let lo = 0;
  let hi = prices.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (prices[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}

const prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49];
console.log(`find: ${find(prices, 15)}`);
const first = lowerBound(prices, 15);
console.log(`Първото 15 €: индекс ${first}`);
console.log(`Продукти по 15 €: ${lowerBound(prices, 16) - first}`);
const from20 = lowerBound(prices, 20);
console.log(`Първата цена от 20 € нагоре: ${prices[from20]} €`);

find: 5
Първото 15 €: индекс 4
Продукти по 15 €: 3
Първата цена от 20 € нагоре: 24 €

Ако цената е по-малка от търсената, тя и всичко преди нея отпадат: lo = mid + 1. Иначе mid може да е отговорът, затова остава в обхвата: hi = mid. Цикълът свършва, когато lo и hi се срещнат, а там е първото място с цена ≥ търсената. Ако такова няма, lo е дължината на масива. Колко продукта са по 15 €, е разликата между две долни граници: на 16 и на 15.

JavaScript няма вградено двоично търсене. indexOf, includes и find на масива минават от началото: те са линейни, дори когато масивът е подреден. Пишеш lowerBound сам, както е горе:

const prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49];
console.log(prices.indexOf(24));
console.log(lowerBound(prices, 20));
console.log(lowerBound(prices, 15));

8
8
4

Виж го

Измери: линейно срещу двоично

Линейното и двоичното търсене в същия подреден ценоразпис, когато търсената цена я няма. Линейното сравнява всяка цена: n сравнения. Двоичното прави 20 сравнения при 1 000 000 цени:

Линейно търсене (всяка цена) O(n)
Двоично търсене O(log n)

Алгоритъм	n = 10	n = 1000	n = 100 000	n = 1 000 000
Линейно търсене (всяка цена)	10	1000	100 000	1 000 000
Двоично търсене	4	10	17	20

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

function find(prices, target) {
  let lo = 0;
  let hi = prices.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (prices[mid] === target) {
      return mid;
    } else if (prices[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

Кривата на двоичното почти лежи: при 100 пъти повече цени тя се качва с около 7 сравнения. Затова двоичното търсене е навсякъде, където нещо е подредено: индексите в базите данни, git bisect, търсенето на версия, от която тестът пада.

Упражнение

Ценовият филтър: от 10 € до 30 €

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

От 10 € до 30 €. Филтърът показва колко продукта има с цена от 10 € до 30 € включително. Ценоразписът е подреден: 3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44 и 49 €. Не обхождай целия масив: с две двоични търсения намери първото място с цена ≥ 10 € и първото с цена ≥ 31 €. Разликата е броят.

От 10 € до 30 €: 7 продукта

Още задачи

Последното срещане. Напиши upperBound: първото място с цена, по-голяма от търсената. Последният продукт по 15 € е на едно място преди него.
Свободен час за доставка. Свободните часове за доставка са подреден масив от минути от полунощ (540 е 9:00). Клиентът иска доставка не по-рано от 14:10. Намери първия свободен час или кажи, че няма.
Къде влиза новата цена. Нов продукт за 21 € трябва да влезе в ценоразписа, без той да спре да е подреден. Намери мястото с двоично търсене.

Тест

Провери се

1. Ценоразписът има 1 000 000 цени, подредени по големина. Най-много колко сравнения прави двоичното търсене?201000500 000

2. Обхватът е затворен: hi започва от последния индекс. Кое условие на цикъла е вярно?lo <= hilo < hilo != hi

3. При while (lo <= hi) някой пише hi = mid вместо hi = mid - 1. Какво става?Когато lo и hi се срещнат, а цената на mid е по-голяма, hi остава същото и цикълът не спираНищо, търсенето е само малко по-бавноПрограмата не се компилира

4. Цените имат три продукта по 15 €. Кой търсиш, за да покажеш всички продукти „от 15 € нагоре“?Което и да е 15, което двоичното търсене намериПоследното 15 €Първото място с цена ≥ 15 € (долната граница)

5. Списъкът с продукти не е подреден. Става ли двоично търсене?Не: отговорът е грешен, защото половината, която изхвърляш, може да съдържа ценатаДа, само е по-бавноДа, ако списъкът е малък

Двоично търсене

Бисквитки