O que é Binary search?


0

Este artigo irá explicar o que é Binary search e como usar Binary search.

Busca binária

Uma pesquisa binária, também conhecida como pesquisa de meio intervalo, é um algoritmo usado em ciência da computação para localizar um valor especificado (chave) em uma matriz. Para que a pesquisa seja binária, a matriz deve ser classificada em ordem crescente ou decrescente.

Como funciona?

Ilustração de uma busca binária

Como você pode ver no diagrama, a cada etapa do algoritmo é feita uma comparação. Em seguida, o procedimento se ramifica em uma das duas direções. Especificamente, o valor da chave é comparado ao elemento do meio da matriz. Se o valor da chave for menor ou maior do que este elemento do meio, o algoritmo sabe qual metade da matriz deve continuar pesquisando. O motivo é porque a matriz está classificada. Este processo é repetido em segmentos progressivamente menores da matriz até que o valor seja localizado.

Como cada etapa do algoritmo divide o tamanho da matriz pela metade, uma pesquisa binária é concluída com êxito em tempo logarítmico. Ou seja, o pior cenário para um array de n elementos está garantido dentro das operações log (n).


Like it? Share with your friends!

0

What's Your Reaction?

hate hate
0
hate
confused confused
0
confused
fail fail
0
fail
fun fun
0
fun
geeky geeky
0
geeky
love love
0
love
lol lol
0
lol
omg omg
0
omg
win win
0
win
Rubem Rego

0 Comments

Your email address will not be published. Required fields are marked *