1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Pesquisa Binária - Pascal

Discussão em 'Programação' iniciada por Jaab, 1 de Dezembro de 2008. (Respostas: 13; Visualizações: 4001)

  1. 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
     
  2. Jaab

    Jaab Power Member

  3. solidforms

    solidforms Power Member

    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
     
  4. Jaab

    Jaab Power Member

    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
     
  5. souto

    souto To fold or to FOLD?

    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: 1 de Dezembro de 2008
  6. Jaab

    Jaab Power Member

    Foste bastante explicito obrigado!
     
  7. souto

    souto To fold or to FOLD?

    Onde disse algoritmo de pesquisa linear, queria dizer binária.
    Já está rectificado no original.
     
    Última edição: 1 de Dezembro de 2008
  8. Jaab

    Jaab Power Member

    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: 3 de Dezembro de 2008
  9. razor_pt

    razor_pt Power Member

    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
     
  10. AliFromCairo

    AliFromCairo Power Member

    Podes sempre editar (e corrigir) o artigo da wikipedia.
     
  11. razor_pt

    razor_pt Power Member

    Pois, se eu soubesse como é que o algoritmo se faz lol. Só apontei um erro que um principiante consegue logo topar
     
  12. Jaab

    Jaab Power Member

    ninguém me pode ver erro desse código por favor...preciso mesmo
     
  13. Jaab

    Jaab Power Member

    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: 4 de Dezembro de 2008

Partilhar esta Página