Binary Search

Vou começar aqui uma série sobre algoritmos e estrutura de dados(me baseando no livro entendendo algoritmos), para isso nada melhor do que começar com o algoritmo de busca binária.

O algoritmo de busca binária é um algoritmo de pesquisa, sua entrada é uma lista ordenada de elementos. Ao encontrar o elemento a pesquisa retorna sua localização na lista. Mas como assim?

Vamos usar o clássico exemplo da lista telefônica aqui pois ele é universal e relativamente simples de ser entendido. Vamos supor que você precise encontrar um nome numa lista telefônica, qual a maneira mais rápida de fazer isso?

Podemos tentar checar todos os nomes da lista de um a um, isso obviamente funcionaria em algum momento, se o nome que estivéssemos procurando fosse Arnaldo, por exemplo, conseguiríamos encontrar com certa facilidade, agora se estivéssemos procurando pelo Zé iriamos despender uma quantidade significativa de tempo dependendo do tamanho da lista. Isso se dá ao fato de uma lista telefônica geralmente ser uma lista de elementos ordenados de A - Z, ou seja em ordem alfabética, buscar cada item de um a um tem um tempo O(n), em notação BigO, ou seja, o tempo de execução de nosso algoritmo cresce linearmente de acordo com a quantidade de items.

Existem porém, maneiras mais eficientes de se encontrar um item em uma lista ordenada, como uma lista telefônica, é ai que entra nosso algoritmo de busca binária. E se ao invés de checar cada item um a um a gente começasse pelo meio da lista telefônica? Vamos supor que estamos procurando por um Jorge, abrimos nossa lista telefônica no meio e caímos diretamente na letra M, a letra M vem depois da letra J no alfabeto então o que fazemos? Vamos pegar a porção do livro que corresponde a parte anterior a letra M, que vai de A -> M e abrir na metade novamente, iremos provavelmente parar na letra G que dessa vez vem antes da letra J, agora pegamos a parte do livro a direita, que vem depois de G, ficaremos com a porção da lista telefônica que corresponde aos nomes entre G -> M, com isso teremos [G, H, I, J, K, L, M], perceba que a letra J está bem no meio da porção do livro que temos em mão, ao abrir essa porção da lista na metade provavelmente encontraremos a letra J.

Como aplicar isso em um código? Segue uma implementação simples de Binary Search em javascript com algumas explicações:

var binarySearch = function(nums, alvo) {
  /* com os dois números abaixo iremos determinar a fatia de nosso array durante a execução da função,
  começando pelo array inteiro sendo o início o índice 0 e o final o índice do último item de nosso array*/
  //o indíce do começo de nosso array, a esquerda
  let esquerda = 0
  //o indíce que mantém o rastreio do final de nosso array, a direita
  let direita = nums.length - 1
  while(esquerda <= direita){
      // Calcula o índice do meio
      let meio = Math.floor((esquerda + direita) / 2)
      // Verifica se o elemento do meio é o alvo, caso sim retorna o índice do mesmo
      if(nums[meio] === alvo){
          return meio
      }
      /* Se o elemento do meio for menor que o alvo, ignore a metade esquerda do array, atribuindo
      a nosso índice de controle do início do array o índice do meio + 1*/
      if(nums[meio] < alvo){
          esquerda = meio + 1
      }
      /* Se o elemento do meio for maior que o alvo, ignore a metade direita do array
      atribuindo a nossa váriavel de controle de fim do array o índice do meio - 1*/
      if(nums[meio] > alvo){
        direita = meio - 1
    }
  }
  // Retorna -1 se o elemento não for encontrado
  return -1;
};

Espero que esse artigo possa ter ajudado a esclarecer um pouco mais o algoritmo Binary Search para você que está lendo! Irei seguir publicando essa série de artigos por aqui!