Wyszukiwanie liniowe i binarne

Algorytmy z egzaminu różnymi sposobami - JavaScript od podstaw: konsola (JavaScript)

W posortowanej tablicy nie trzeba sprawdzać po kolei. Wyszukiwanie binarne (połówkowe) patrzy na środek przedziału i odrzuca połowę, w której szukanej liczby na pewno nie ma, tak jak w zgadywaniu liczby z tematu o pętli while. Dla tablicy 1000 liczb liniowe potrzebuje do 1000 porównań, binarne najwyżej 10.

const numbers = Array.from({ length: 1000 }, (_, i) => i * 3);

function linear(arr, x) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === x) return [i, i + 1];
  }
  return [-1, arr.length];
}

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

for (const x of [27, 2400, 2997, 1000]) {
  const [i, a] = linear(numbers, x);
  const [j, b] = binary(numbers, x);
  console.log(`${x}: indeks ${i} ${j}, porównań liniowo ${a}, binarnie ${b}`);
}

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu JavaScript od podstaw: konsola·Zaloguj się, aby zapisać postęp na koncie.