Mudanças entre as edições de "Tópicos Binária em Vetor"
Ir para navegação
Ir para pesquisar
| (4 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
| Linha 26: | Linha 26: | ||
=Algoritmo da Busca Binária= | =Algoritmo da Busca Binária= | ||
| + | [https://en.wikipedia.org/wiki/Binary_search_algorithm Ver] | ||
| + | |||
<syntaxhighlight lang=C> | <syntaxhighlight lang=C> | ||
FUNCAO busca_binaria | FUNCAO busca_binaria | ||
| Linha 33: | Linha 35: | ||
inteiro x: valor a ser procurado | inteiro x: valor a ser procurado | ||
DADOS DE SAÍDA | DADOS DE SAÍDA | ||
| − | + | índice do item encontrado (-1 se não encontrado) | |
VARIÁVEIS AUXILIARES | VARIÁVEIS AUXILIARES | ||
inteiro i, | inteiro i, | ||
| Linha 42: | Linha 44: | ||
inicio=0 /* supondo que o vetor começa na posição 0 */ | inicio=0 /* supondo que o vetor começa na posição 0 */ | ||
fim=n-1 | fim=n-1 | ||
| − | meio=(inicio+fim)/2 /* deve ser arredondado para o primeiro inteiro menor ou igual a divisão (floor) */ | + | ENQUANTO (inicio <= FIM) FAZ |
| − | + | meio=(inicio+fim)/2 /* deve ser arredondado para o primeiro inteiro menor ou igual a divisão (floor) */ | |
| − | SE V[meio]== x ENTAO | + | SE V[meio]==x ENTAO /* se o item está no meio, então nada mais a fazer... retornar o índice do meio */ |
retornar meio; | retornar meio; | ||
SENAO SE V[meio] > x ENTAO | SENAO SE V[meio] > x ENTAO | ||
| Linha 50: | Linha 52: | ||
SENAO SE V[meio] < x ENTAO | SENAO SE V[meio] < x ENTAO | ||
inicio = meio + 1 /* reajusta os limites de forma a determinar um subvetor superior */ | inicio = meio + 1 /* reajusta os limites de forma a determinar um subvetor superior */ | ||
| + | FIM_ENQUANTO | ||
| + | retornar -1 /* se chegou aqui é porque não encontrou ... Retorna -1 */ | ||
FIM | FIM | ||
</syntaxhighlight> | </syntaxhighlight> | ||
EXERCÍCIO 1: Implementar uma função C para o algoritmo de busca acima. Testar 4 vezes de forma a cobrir todas as possibilidades de saída. | EXERCÍCIO 1: Implementar uma função C para o algoritmo de busca acima. Testar 4 vezes de forma a cobrir todas as possibilidades de saída. | ||
Edição atual tal como às 14h51min 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).
Ver figura de busca linear aqui
Algoritmo da Busca Binária
FUNCAO busca_binaria
DADOS DE ENTRADA:
V: Vetor de itens /* para manter conformidade com o C, assumimos que a indexação começa em 0 */
inteiro n: tamanho do vetor
inteiro x: valor a ser procurado
DADOS DE SAÍDA
índice do item encontrado (-1 se não encontrado)
VARIÁVEIS AUXILIARES
inteiro i,
inicio,
fim,
meio
INÍCIO
inicio=0 /* supondo que o vetor começa na posição 0 */
fim=n-1
ENQUANTO (inicio <= FIM) FAZ
meio=(inicio+fim)/2 /* deve ser arredondado para o primeiro inteiro menor ou igual a divisão (floor) */
SE V[meio]==x ENTAO /* se o item está no meio, então nada mais a fazer... retornar o índice do meio */
retornar meio;
SENAO SE V[meio] > x ENTAO
fim = meio -1 /* reajusta os limites de forma a determinar um subvetor inferior */
SENAO SE V[meio] < x ENTAO
inicio = meio + 1 /* reajusta os limites de forma a determinar um subvetor superior */
FIM_ENQUANTO
retornar -1 /* se chegou aqui é porque não encontrou ... Retorna -1 */
FIM
EXERCÍCIO 1: Implementar uma função C para o algoritmo de busca acima. Testar 4 vezes de forma a cobrir todas as possibilidades de saída.