Relatório - OAC

Prévia do material em texto

1. Introdução
A pesquisa ou busca binária é um algoritmo de busca em vetores que requer acesso aleatório aos elementos dele. 
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. A complexidade desse algoritmo é da ordem de log2n, onde n é o tamanho do vetor de busca. Como resultado do seu programa, ele deve devolver o índice no array em que o elemento foi encontrado.
Pseudo-código do algoritmo:
· BUSCA-BINÁRIA (V[ ], inicio, fim, valor}
· i recebe o índice no meio de inicio e fim
· se V[i] é igual a valor
· então devolva o índice i # encontrei valor
· senão se V[i] vem antes de valor
· então faça a BUSCA-BINÁRIA (V, i+1, fim, valor)
· senão faça a BUSCA-BINÁRIA (V, início, i-1, valor)
Durante o desenvolvimento desse trabalho faremos a tradução do algoritmo de busca binária e explicaremos o passo a passo de sua implementação na linguagem de baixo nível MIPS. Para tal, como solicitado, utilizaremos o simulador MARS V4.5 que nos permite programar neste tipo de linguagem.
2. Desenvolvimento
Referências:
[1] http://pt.wikipedia.org/wiki/Pesquisa_binária
[2] Sedgewick, R. (1988) Algorithms. Addison-Wesley, Reading, Massachusetts.