Javascript de pesquisa binária

Michael Zippo

Como codificar uma busca binária em JavaScript

Algoritmos de busca facilitam muito a vida de um programador. Isso facilita a localização de um item específico em um conjunto de dados de dezenas, centenas ou milhares de itens.

Uma das formas mais populares de pesquisa é a pesquisa binária. Essa pesquisa localiza rapidamente um elemento em uma matriz. Cada vez que a pesquisa examina um item, ela reduz pela metade o número de itens a serem encontrados.

Neste guia, falaremos sobre o que são pesquisas binárias e como elas funcionam. Em seguida, passaremos a implementar uma pesquisa binária usando duas abordagens diferentes: iterativa e recursiva.

Vamos criar um algoritmo de pesquisa binária em !

O que é uma pesquisa binária ?

Uma pesquisa binária é um algoritmo de computador que procura um elemento em um array ordenado.

Comece no meio de uma matriz e verifique se o elemento do meio é menor, igual ou maior que o número que você está procurando.

Se o número for menor, o algoritmo sabe continuar procurando na metade esquerda do array, onde estão os números menores; se o número for maior, o algoritmo se concentrará na metade direita da matriz. As pesquisas binárias funcionam apenas em listas ordenadas.

As pesquisas binárias são mais eficientes do que as pesquisas lineares. Na verdade, cada vez que uma pesquisa é realizada, o número de itens restantes a serem encontrados na lista é reduzido pela metade.

Como usar uma pesquisa binária

Uma pesquisa binária é fácil de entender depois que você a aprende.

Antes de implementar um algoritmo de pesquisa binária, vamos revisar - dê um passo. Encontraremos o número "9" em uma lista. Vamos começar com uma lista ordenada:

6 < / td>

Primeiro, precisamos encontrar o número do meio e atribuí-lo a uma variável. Isso é encontrado calculando a soma do primeiro e do último número e dividindo por dois. Chamaremos essa variável "central":

Iniciar	< br>	Médio		Fim
2	6	8	9	10

8 é o nosso número médio. Assim, podemos comparar o número central com aquele que estamos procurando. Se o número central for o mesmo que estamos procurando, nossa busca pode parar.

Neste exemplo, 8 não é igual a 9. Nossa busca continua.

Então temos que comparar se o número do meio é maior que 9. Não é.

Isso nos diz que o número que estamos procurando deve estar depois do número central número. 9 é maior que 8 em uma lista ordenada. defina nosso número inicial igual ao número central. Isso porque sabemos que o número que estamos procurando não vem antes do número central.

Se o número que procuramos for mais bebê, definiremos o número final igual ao número do meio. Como o número é menor que o número do meio, poderíamos focar nossa pesquisa na metade inferior da lista.

A pesquisa binária se repete novamente na metade superior da lista porque 9 é maior que 8:

< td> Médio

Iniciar Fim

8 < /td>

Vamos encontrar o número central. Isso é 9. Podemos comparar 9 com o número que estamos procurando. 9 é igual ao número que estamos procurando.

Isso significa que nossa pesquisa pode parar. Conseguimos encontrar o número 9 em nossa lista!

Como implementar uma pesquisa binária em JavaScript

As pesquisas binárias podem ser implementadas usando uma abordagem iterativa ou recursiva.

Pesquisa binária iterativa

Uma pesquisa binária iterativa usa um loop while para encontrar um item em uma lista. Esse loop será executado até que o item seja encontrado na lista ou até que a lista seja pesquisada.

Vamos começar escrevendo uma função que realiza nossa pesquisa binária:

Vamos começar definindo duas variáveis: início e fim. Estes registram os valores mais altos e mais baixos com os quais nossa pesquisa está trabalhando. Usamos um while loop que é executado até que o número inicial seja maior que o número final. Esse loop calcula o número intermediário entre o início e o fim da lista.

Se o número que estamos procurando for igual ao número do meio, o número do meio é retornado ao nosso programa principal. o número é menor, o valor da semente é definido como o número do meio mais 1. Essas comparações são feitas usando uma instrução if .

Caso contrário, o número final é definido como o número do meio menos um. Se nosso número não for encontrado após a execução do loop while, ele retornará -1. Chamamos isso de condição básica. Em nosso programa principal, `vai verificar se o número retornado é igual a -1. é, significa que nosso número não foi encontrado.

Nossa função ainda não funciona. Precisamos escrever um programa principal para nomeá-lo:

Definimos uma lista de números para pesquisar e o número que queremos encontrar em nossa lista. Em seguida, chamamos a função binarySearch. Isso fará nossa pesquisa. A pesquisa retornará -1 ou a posição do elemento que estamos procurando.

-1 indica que um item não foi encontrado. Se um elemento não for encontrado, o conteúdo de nossa instrução else será executado. Caso contrário, o conteúdo da instrução if é executado.

Vamos executar nosso código:

Isso nos diz que nossa pesquisa foi bem-sucedida!

Pesquisa binária recursiva

Uma busca binária recursiva é considerada mais elegante do que uma busca iterativa. Isso ocorre porque as pesquisas binárias executam a mesma operação repetidamente em uma lista. Esse comportamento pode ser implementado usando um algoritmo de recursão.

Abra um novo arquivo JavaScript e cole este código:

Este código faz as mesmas comparações que nossa primeira pesquisa. Verifique se o número do meio é igual, maior ou menor que o número que estamos procurando.

No início do nosso function , usamos uma instrução if para verificar se o número inicial é maior que o número final. Se for, isso significa que nosso item não foi encontrado na lista que especificamos. Neste caso, estamos retornando -1 ao programa principal.

Se o número que procuramos for igual ao número central, o número central é retornado ao programa principal. o número que estamos procurando for maior ou menor que o número central, nossa função de busca binária é executada novamente. Isso continua até que nosso elemento seja encontrado.

Para realizar esta função, precisaremos faça uma modificação em nosso programa principal:

Precisamos passar mais dois parâmetros: os valores ‚Äã‚Äão de "start" e "end". O valor de "start" é igual a 0. O valor de "end" é igual ao comprimento da lista menos um.

Vamos executar nosso código e ver o que acontece:

Nossa busca binária foi bem sucedida! Ele usa o mesmo algoritmo subjacente que a abordagem iterativa. A diferença é que a busca binária é realizada usando uma função chamada até que o item seja encontrado ou até que a busca na lista seja concluída, o que ocorrer primeiro.

Conclusão

As pesquisas binárias facilitam a localização de um item em uma lista. Cada vez que uma pesquisa é realizada, o número de itens restantes a serem encontrados em uma lista é reduzido pela metade. Isso torna uma pesquisa binária mais eficiente do que uma pesquisa linear.

Agora você está pronto para implemente a pesquisa binária em JavaScript como um especialista!