Mudanças entre as edições de "Tópicos Binária em Vetor"
Ir para navegação
Ir para pesquisar
(Criou página com '=Objetivos= Após esta aula o aluno deverá: #saber explicar o princípio da busca binária em vetor; #ser capaz de implementar a busca binária em C =Referências= CORMEN...') |
|||
| Linha 22: | Linha 22: | ||
Note que o algoritmo deve então repetir a busca conforme as condições acima até que INICIO seja maior que o FIM (note que estes limites mudam a cada subvetor). | Note que o algoritmo deve então repetir a busca conforme as condições acima até que INICIO seja maior que o FIM (note que estes limites mudam a cada subvetor). | ||
| − | =Algoritmo da Busca | + | =Algoritmo da Busca Binária= |
FUNCAO | FUNCAO | ||
Edição das 09h25min de 14 de abril de 2022
Objetivos
Após esta aula o aluno deverá:
- saber explicar o princípio da busca binária em vetor;
- ser capaz de implementar a busca binária em C
Referências
CORMEN, Thomas. Desmistificando Algoritmos. [Digite o Local da Editora]: Grupo GEN, 2013. 9788595153929. Disponível em: https://app.minhabiblioteca.com.br/#/books/9788595153929/. Acesso em: 14 abr. 2022.
Conceitos Iniciais sobre a busca binária
É importante observar inicialmente que o vetor onde será realizada a busca deve estar ORDENADO.
A ideia subjacente é começar a pesquisa no MEIO do vetor. Três possibilidade podem ocorrer.
- O item procurado está no meio do vetor, este caso o índice do meio deve ser retornado.
- O item a ser procurado é MAIOR que o elemento do MEIO então a busca deve ser realizada no subvetor compreendido entre o MEIO +1 e o FINAL.
- O item a ser procurado é MENOR que o elemento do MEIO então a busca deve ser realizada no subvetor compreendido entre o INICIO e o MEIO -1.
Note que o algoritmo deve então repetir a busca conforme as condições acima até que INICIO seja maior que o FIM (note que estes limites mudam a cada subvetor).
Algoritmo da Busca Binária
FUNCAO