Wyszukiwanie binarne w JavaScript

Wyszukiwanie binarne to algorytm wyszukiwania, który służy do znajdowania pozycji określonego elementu na posortowanej liście. Działa poprzez wielokrotne dzielenie listy na pół, aż do znalezienia żądanego elementu lub stwierdzenia, że ​​elementu nie ma na liście.

Jak działa wyszukiwanie binarne?

Aby zrozumieć, jak działa wyszukiwanie binarne, rozważmy przykład. Załóżmy, że mamy posortowaną listę liczb całkowitych i chcemy znaleźć pozycję liczby 37. Oto jak działałby algorytm wyszukiwania binarnego:

1. Najpierw określamy środkowy element listy. Jeśli środkowy element to 37, skończyliśmy i zwracamy pozycję elementu.
2. Jeśli środkowy element nie jest równy 37, sprawdzamy, czy jest większy lub mniejszy niż 37. Jeśli jest większy niż 37, wiemy, że żądany element musi znajdować się w lewej połowie listy. Jeśli jest mniejsza niż 37, wiemy, że żądany element musi znajdować się w prawej połowie listy.
3. Proces powtarzamy na odpowiedniej połowie listy, aż do znalezienia elementu lub stwierdzenia, że ​​elementu nie ma na liście.

function binarySearch(arr, x) {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    
    if (arr[mid] === x) {
      return mid;
    }
    else if (arr[mid] < x) {
      start = mid + 1;
    }
    else {
      end = mid - 1;
    }
  }
  
  return -1;
}

let arr = [1, 3, 5, 7, 9, 11, 13];
let x = 5;

console.log(binarySearch(arr, x)); // Output: 2

Dlaczego powinniśmy używać wyszukiwania binarnego?

Dlaczego więc powinniśmy używać wyszukiwania binarnego? Jedną z głównych zalet wyszukiwania binarnego jest jego złożoność czasowa. W najgorszym przypadku złożoność czasowa wyszukiwania binarnego wynosi O(log n), co oznacza, że ​​jest ono znacznie szybsze niż wyszukiwanie liniowe (O(n)) w przypadku dużych list. Dzięki temu jest to wydajny algorytm do przeszukiwania dużych zbiorów danych.

Podsumowując, wyszukiwanie binarne jest przydatnym algorytmem do szybkiego znajdowania pozycji określonego elementu na posortowanej liście. Jego złożoność czasowa sprawia, że ​​nadaje się do wyszukiwania dużych zbiorów danych i jest stosunkowo łatwa do zaimplementowania w JavaScript.