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?
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).
0 Comments