Pesquisa Binária - Pascal

Jaab

Jaab

Power Member
Boas...tenho que fazer um trabalho para a escola e este consiste em fazer um programa em pascal que implemente este algoritmo e que explique o modo de funcionamento.

Poderiam dar-me umas luzes sobre isto?

Pesquisei por todo o lado e não encontro informações concretas sobre isto.

Obrigado
 
O problema esta na implementaçao do codigo, ou na teoria?
No codigo, alias linguagem, nao posso ajudar muito.

Na teoria, penso que posso. Na pesquisa binaria, existe a necessidade de o vector estar ordenado. Custa menos inserir ordenadamente do que ir ordenando sempre que pesquisas.
A pesquisa binaria consiste em dividir o vector em 2 (binario). Calculas o meio, usando o resto da divisao pelo currentSize. Ves se o meio é o valor que queres, se o que queres procurar é menor que o meio, fazes o mesmo para a primeira metade, senao vais para a segunda metade. E vais sempre repetindo o processo ate o meio que calculares seja o valor que queres ou null se nao existir (divisao e conquista).

Surpreende-me nao econtrares informaçao. Sem ser no wikipedia, existem muitos sites com este algoritmo, é bastante conhecido.

Nao percebi a duvida, mas tentei ;).

Cumps :p
 
solidforms disse:
O problema esta na implementaçao do codigo, ou na teoria?
No codigo, alias linguagem, nao posso ajudar muito.

Na teoria, penso que posso.
(...) Surpreende-me nao econtrares informaçao. Sem ser no wikipedia, existem muitos sites com este algoritmo, é bastante conhecido.

Nao percebi a duvida, mas tentei ;).

Cumps :p
Clicar para expandir...

obrigado na mesma, mas ainda tenho duvidas.
não percebo muito bem o vector, que dados ele vai ler para serem procurados. Como ele faz a essa divisão que falaste ? ah encontrei informação o problema foi percebe-la
 
A pesquisa binária pode ser percebida com um exemplo relativamente simples.

Pegas num livro qualquer, com umas 800 páginas. Imagina que estás à procura da página 436.
Abres o livro no meio, não sabendo ao certo que página vais abrir.

Descobres que é a página 356. Como estás à procura da página 436, sabes que todas as páginas até à pag. 356 não te servem de nada, logo não vais voltar a procurar nelas.

Tens agora apenas um subconjunto das 800 páginas, nomeadamente da página 357 à 800. Escolhes aproximadamente o meio desse subconjunto. Calhas na página 635, por exemplo.

Todas as páginas para a frente da página 635 não te servem de nada (pois estás à procura da página 436), logo não precisas de pesquisar de novo daí para a frente.

Ficas então com o subconjunto das páginas entre 357 e 635. Abres aproximadamente a meio, e calha-te na página 436. Bingo.

Quantas procuras fizeste? 3 ou 4. Se começasses a pesquisar da primeira página, terias que pesquisar as 357 páginas, ou seja, 357 pesquisas.

O algoritmo de pesquisa linear binária necessita apenas que os dados sejam ordenados, caso contrário não podes fazer os cortes que exemplifiquei acima (se pensares um pouco percebes imediatamente porquê).


Em termos de implementação, a recursiva é sem dúvida a melhor, mas podes fazer iterativamente também.

Espero ter sido explícito.
 
Última edição:
souto disse:
A pesquisa binária pode ser percebida com um exemplo relativamente simples.

Pegas num livro(...)O algoritmo de pesquisa linear necessita apenas que os dados sejam ordenados, caso contrário não podes fazer os cortes que exemplifiquei acima (se pensares um pouco percebes imediatamente porquê).


Em termos de implementação, a recursiva é sem dúvida a melhor, mas podes fazer iterativamente também.

Espero ter sido explícito.
Clicar para expandir...

Foste bastante explicito obrigado!
 
Onde disse algoritmo de pesquisa linear, queria dizer binária.
Já está rectificado no original.
 
Última edição:
podiam-me dizer o que está mal aqui?
Código: 
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}
            repeat
               meio := (inicio+fim) div 2;
                 if (Chave = vetor[meio]) then 
                      BuscaBinaria := meio;
                 if (Chave < vetor[meio]) then 
                      fim:=(meio-1); 
                 if (Chave > vetor[meio]) then
                      inicio:=(meio+1);
          until (Chave = Vetor[meio]) or (inicio > fim);
            if (Chave = Vetor[meio]) then 
                BuscaBinaria := meio 
            else 
                BuscaBinaria := -1; {Retorna o valor encontrado, ou -1 se a chave nao foi encontrada.}
     end;
 
Última edição pelo moderador:
Exacto, tiraste isso da wikipedia não foi? Para começar o último end deveria ter . e não ; certo? Não percebo como metem um algoritmo na wiki que depois não corre
 
function search( key : typekey; var r : dataarray ) : integer;
var high, j, low : integer;
Código: 
     begin
     low := 0;
     high := n;
     while high-low > 1 do begin
          j := (high+low) div 2;
          if key <= r[j].k then high := j
                           else low  := j
          end;
     if r[high].k = key then search := high  {*** found(r[high]) ***}
                        else search := -1;   {*** notfound(key) ***}
     end;

o que está errado neste algoritmo??
 
Última edição pelo moderador:
Inicie sessão ou registe-se para poder participar.
Back
Topo