Pesquisa binária em JavaScript

A pesquisa binária é um algoritmo de pesquisa usado para encontrar a posição de um elemento específico em uma lista classificada. Ele funciona dividindo repetidamente a lista ao meio, até que o elemento desejado seja encontrado ou seja determinado que o elemento não está presente na lista.

Como funciona a busca binária?

Para entender como a pesquisa binária funciona, vamos considerar um exemplo. Suponha que temos uma lista ordenada de números inteiros e queremos encontrar a posição do número 37. Veja como o algoritmo de busca binária funcionaria:

1. Primeiro, determinamos o elemento do meio da lista. Se o elemento do meio for 37, terminamos e retornamos a posição do elemento.
2. Se o elemento do meio não for 37, verificamos se é maior ou menor que 37. Se for maior que 37, sabemos que o elemento desejado deve estar na metade esquerda da lista. Se for menor que 37, sabemos que o elemento desejado deve estar na metade direita da lista.
3. Repetimos o processo na metade apropriada da lista até que o elemento seja encontrado ou seja determinado que o elemento não está presente na lista.

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

Por que devemos usar a pesquisa binária?

Então, por que devemos usar a pesquisa binária? Uma das principais vantagens da busca binária é sua complexidade de tempo. No pior cenário, a complexidade de tempo da pesquisa binária é O(log n), o que significa que ela é muito mais rápida que a pesquisa linear (O(n)) para listas grandes. Isso o torna um algoritmo eficiente para pesquisar grandes conjuntos de dados.

Em conclusão, a pesquisa binária é um algoritmo útil para encontrar rapidamente a posição de um elemento específico em uma lista classificada. Sua complexidade de tempo o torna adequado para pesquisar grandes conjuntos de dados e é relativamente fácil de implementar em JavaScript.