Pesquisa Binária e Matriz

Trabalho de LTP1
Nome: Thayto Luis
Professor: Dutra Turma: 131

Pesquisa binária
Conceito:
Uma pesquisa binária funciona de forma semelhante à pesquisa por uma palavra num dicionário. Quando procura por "Verde", você não abre o dicionário na primeira página e começa a procurar a sua palavra por todo o dicionário. Em vez disso você tira partido do conhecimento de que as palavras estão ordenadas alfabeticamente.
Isto é como descreveria a pesquisa a outra pessoa: Primeiro abra o dicionário em metade, e olhe para a primeira palavra que encontra. Compare-a com a palavra por que está a procurar. Se for igual, encontrou-a. Se não, divida uma das duas metades do dicionário de novo em metade (a metade direita se a palavra por que estava a procurar está depois da que encontrou, a metade esquerda se antes, alfabeticamente), e repita o processo.
Aplicação:
Lembra-se do jogo das advinhas, da infância? "Adivinhem um número". "Estou a pensar num número entre 1 e 100 - adivinhem qual é em 10 tentativas". "Só vos posso dizer se o número que adivinham está acima ou abaixo do número em que pensei".
A melhor estratégia para ganhar neste jogo é exatamente a mesma. Você começa por adivinhar 50, e depois passa a metade disso, depois metade, e assim por diante, baseado nas respostas que recebe. Se fizer isto irá sempre encontrar o número em menos de 8 tentativas! Isto é chamada uma pesquisa binária.

Exemplo: (Em Pascal)
FUNCTION BUSCABINARIA (VETOR: ARRAY OF STRING; CHAVE: STRING; DIM: INTEGER): INTEGER;
VAR
* * *INICIO, FIM: INTEGER; { AUXILIARES QUE REPRESENTAM O INICIO E O * * *FIM DO VETOR ANALISADO }
* * *MEIO: INTEGER; { MEIO DO VETOR }
BEGIN
* * * *FIM:= DIM; { O VALOR DO ÚLTIMO ÍNDICE DO VETOR }
* * * *INICIO:= 1; { O VALOR DO PRIMEIRO ÍNDICE DO VETOR }
* * * *BUSCABINARIA:= -1; { RETORNA O VALOR -1 SE A CHAVE NAO FOR * * * *ENCONTRADA. }
* * * *REPEAT
* * * * * * * * *MEIO:= (INICIO+FIM) DIV 2;
* * * * * * * * *IF (CHAVE = VETOR[MEIO]) THEN