-
Gabarito B
A busca binária é um eficiente algoritmo para encontrar um item em uma lista ordenada de itens. Ela funciona dividindo repetidamente pela metade a porção da lista que deve conter o item, até reduzir as localizações possíveis a apenas uma. Nós usamos a busca binária em um jogo de adivinhação no tutorial introdutório.
Um dos modos mais comuns de se usar a busca binária é para encontrar um item em um array. Por exemplo, o catálogo estelar Tycho-2 contém informações sobre as 2.539.913 estrelas mais brilhantes na nossa galáxia. Suponha que você queira buscar por uma estrela em particular no catálogo, com base no nome da estrela. Se o programa examinou cada estrela do catálogo de estrelas em ordem começando com o primeiro nome, utilizando um algoritmo chamado busca linear, no pior caso, o computador pode ter examinado todas as 2,539,913 estrelas para encontrar a estrela que você está procurando. Se o catálogo estivesse organizado alfabeticamente pelos nomes das estrelas, a busca binária não teria que examinar mais do que 22 estrelas, mesmo no pior caso.
"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !
-
A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.
fonte: https://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria
-
BUSCA BINÁRIA:
A ideia básica do algoritmo é percorrer o vetor como se folheia, por exemplo, uma lista telefônica. Abandonando-se as partes do catálogo onde o nome procurado, com certeza, não será encontrado.
Para a realização desse tipo de busca, o vetor deve estar ordenado.
Esse método exige acesso aleatório aos elementos do conjunto.
Algoritmo possui complexidade no pior caso O(logn).
O pior caso ocorre quando o elemento procurado é o último a ser verificado, ou mesmo não é encontrado.
Fonte: Itnerante
-
Busca Binária
Utiliza o método do “dividir para conquistar”: busca o elemento do meio da coleção, dividindo-a em duas sub-coleções
• Compara-se o valor procurado com o elemento no centro da coleção:
– Se for igual, encontrou;
– Se for menor, repete a busca na sub-coleção à esquerda do centro;
– Se for maior, repete a busca na sub-coleção à direita do centro;
• Não funciona sobre coleções não-ordenadas!
• Ordem de Complexidade: O(log2 n)
• No pior caso são realizadas “log2 n” comparações
Busca Sequencial
•Caminha de um por um procurando o valor
• Mais lenta quanto maior for a coleção
• Pode ser realizada também em estruturas não ordenadas
• Simples
• Ordem de Complexidade: O(n)
• No pior caso, são realizadas “n” comparações
-
Força Guerreiro!!!!!!