Quando temos um Vetor (ou Matriz) com muitos elementos e precisamos descobrir se um determinado elemento que procuramos se encontra no vetor, uma solução que certamente nos vem à mente é comparar o elemento que procuramos com cada elemento do vetor, até que encontremos ou até que concluamos que o elemento procurado não está no vetor.
Esta é a base do raciocínio dos algoritmos de pesquisa ou busca ("Search"), que como sugere o nome, "Pesquisam", em um vetor, a existência ou não existência de um elemento procurado. A diferença entre um e outro algoritmo de busca, fica por conta da rapidez com que "varremos" o vetor para encontrar o elemento ou para concluirmos que ele não existe.
Um fator que influencia em muito nessa rapidez é a disposição dos elementos no vetor, ou seja se os elementos estão ordenados ou não.
Se os elementos não estão ordenados, não há escolha, temos que comparar o elemento procurado com todos os elementos do vetor. Significa que vamos percorrer todo o vetor e a pesquisa poderá levar tempo caso o vetor contenha muitos elementos.
Se os elementos estão ordenados, não é necessário comparar o elemento procurado com todos os elementos do vetor pois ao encontrarmos um elemento maior do que o elemento procurado, poderemos concluir pela sua não existência no vetor.
Facilitando a Pesquisa com a Ordenação
Os algoritmos de ordenação ou classificação ("Sort"), por sua vez, são utilizados para ordenar os elementos de um vetor de forma a facilitar a pesquisa posterior de um elemento, no conjunto de elementos existentes.
Existem algoritmos para pesquisa e ordenação para as mais variadas estruturas de dados. Na nossa disciplina, entretanto, trataremos apenas os algoritmos de pesquisa e ordenação em vetores, que também podem ser utilizados em matrizes, desde que sofram pequenos ajustes.
Os algoritmos de pesquisa devem considerar sempre duas características importantes:
Com isso temos sempre 4 possibilidades de pesquisa:
Pesquisa ordenada com repetição
Pesquisa ordenada sem repetição
Pesquisa desordenada com repetição
Pesquisa desordenada sem repetição
Para fazermos uma pesquisa em um vetor (ou matriz), precisamos de quatro parâmetros:
O vetor no qual realizaremos a pesquisa
O elemento procurado
O número de elementos desse vetor que devem ser pesquisados. (Lembre-se que muitas vezes um vetor de 1000 elementos, só tem 700 carregados, e podemos evitar tratamento de 300 elementos com "lixo").
Um índice que vai ser preenchido com a posição onde o elemento foi encontrado ou retornará com 0 (zero) caso o elemento não exista. ( parâmetro de saída )
Pesquisa desordenada sem repetição ( Sequencial Simples )
Na pesquisa desordenada ou sequencial simples, como o vetor a ser pesquisado não está ordenado pelo elemento procurado, teremos de percorrer todo o vetor, comparando o elemento procurado com cada elemento do vetor. Portanto para um vetor com n elementos teremos de fazer n testes.
O Algoritmo da Pesquisa Desordenada Sem Repetição é o apresentado abaixo:
Procedimento PESQSEQ (<tipo básico>VET);
/*Executa a Pesquisa da primeira ocorrência de ELEMPROC em VET e retorna em POS o índice onde foi encontrada ou 0 se não existe*/
Pos = 0;
Enquanto (Pos==0) e (J<=TOTELEM) Faça
Se VET[J]==ELEMPROC Então
J = TOTELEM + 1;
Imprima "O elemento está na posicao ", POS;
Senao
Imprima "O elemento nao foi encontrado";
Fim-Se
Pesquisa desordenada com repetição ( Sequencial Simples )
A pesquisa desordenada com repetição trata todas as ocorrências de um elemento procurado no vetor pois não há um único elemento igual ao elemento procurado. Se precisamos determinar todas as ocorrências do elemento procurado em um vetor, o problema se simplifica, pois teremos que, obrigatoriamente, varrer o vetor até o fim (Elimina-se do laço o teste POS = =0), mas teremos de guardar em um vetor todas as posições onde o elemento foi encontrado ou, o que é mais usual, processaremos a ocorrência imediatamente após encontrarmos uma ocorrência do elemento procurado (após POS = J).
O algoritmo da Pesquisa desordenada com repetição é apresentado abaixo:
POS = 0; /*Indicará ao algoritmo chamador a não ocorrência*/
VET_OCORRENCIA[ TOTELEM ];
Inteiro I, J;
I = 0;
Enquanto J <= TOTELEM Faça
Se VET[ J ] == ELEMPROC Então
VET_OCORRENCIA[ I ] = VET[ J ]
Fim Se;
Para C = 0 Ate i - 1 Passo 1 Faca
Imprima "Elemento encontrado ", VET_OCORRENCIA[ C ]
Fim-Faca
Pesquisa Ordenada sem repetição
Para se utilizar a Pesquisa Ordenada sem repetição, o vetor de busca tem de estar ordenado pelo campo chave da pesquisa.
Com isso, ao se encontrar no vetor, um elemento maior do que o elemento procurado, poderemos abandonar a busca pois, com certeza, não mais encontraremos o elemento procurado no vetor.
Devido a isso o número de testes para elementos existentes ou inexistentes será, na média, de TOTELEM/2, e, por isso, melhor que o anterior para o caso de elemento inexistente.
O algoritmo da Pesquisa Ordenada sem repetição é apresentado abaixo:
Procedimento PESQORD (<tipo básico> VET, Inteiro TOTELEM, inteiro POS, <Tipo básico> ELEMPROC);
/*Executa a Pesquisa da primeira ocorrência de ELEMPROC em VET e retorna em POS o índice onde foi encontrada ou 0 se não existe. VET tem de estar ordenado pelo campo chave*/
Enquanto J<=TOTELEM e POS = 0 Faça
Se VET[J] <= ELEMPROC Então
Se VET[J] = ELEMPROC Então
Imprima(" O elemento não está na lista")
Pesquisa Ordenada com repetição
A Pesquisa Ordenada com repetição deve considerar que existe mais de um elemento igual ao elemento procurado.
Porém, deve se considerar que como o vetor está ordenando quando for encontrado um elemento maior do que o elemento procurado devemos finalizar a pesquisa pois não encontraremos mais o elemento procurado no vetor.Com isso, ao se encontrar no vetor, um elemento maior do que o elemento procurado, poderemos abandonar a busca pois, com certeza, não mais encontraremos o elemento procurado no vetor.
Devido a isso o número de testes para elementos existentes ou inexistentes será, na média, de TOTELEM/2, e, por isso, melhor que o anterior para o caso de elemento inexistente.
Procedimento PESQORD (<tipo básico> VET, Inteiro TOTELEM, inteiro POS, <Tipo básico> ELEMPROC);
/*Executa a Pesquisa da primeira ocorrência de ELEMPROC em VET e retorna em POS o índice onde foi encontrada ou 0 se não existe. VET tem de estar ordenado pelo campo chave*/
I = 0;
Enquanto J<=TOTELEM e POS = 0 Faça
Se VET[J] <= ELEMPROC Então
Se VET[J] = ELEMPROC Então
Imprima(" O elemento não está na lista")
Para K = 1 Ate I Passo 1 Faça
imprimir vet_pesq[ k ];
Fim Para
Dado um vetor A de 128 elementos, verificar se existe um elemento igual a K (chave) no vetor. Se existir, imprimir a posição onde foi encontrada a chave; se não, imprimir: “chave K não encontrada” . O vetor A e chave K são fornecidos pelo usuário.
inteiro A[1:128] inteiro;
para I de 1 até 128 passo 1 faça
imprima (K, “ Está na posição” , I);
imprima (“A CHAVE”, K,“NÃO ESTÁ NO VETOR”);
Otimizando a Pesquisa em Vetores Ordenados
Com a Pesquisa Binária a busca por um elemento ficará mais eficiente se pudermos otimizar a pesquisa considerando que o vetor possui elementos ordenados e comparando o elemento procurado com partes do vetor ao invés de varrer o vetor do inicio ao fim.
Para isso utilizarmos a pesquisa binária, desde que o vetor já esteja ordenado. Nesta pesquisa procuramos o elemento K dividindo o vetor em duas partes e testando em qual das duas ele deveria estar. Repetindo este procedimento até encontrar o elemento ou até encontrar o fim lógico do vetor.
Pesquisa Binária
A pesquisa binária é um método que também só se aplica a vetores previamente ordenados. A sua grande vantagem é a rapidez e, por isso, ela é muito recomendada para vetores grandes.
Neste método, a primeira comparação é feita com o elemento do meio do vetor, eliminando-se assim metade do mesmo para a busca. Seguem-se comparações sucessivas ao elemento do meio do segmento onde pode estar o elemento procurado. Assim, a cada comparação feita, metade do vetor é eliminada.
PESQBIN (V: VET, Inteiro: TOTELEM, POS;<Tipo básico>: ELEMPROC)
/*Executa a Pesquisa binária da primeira ocorrência da ELEMPROC em VET e retorna em POS se o índice foi encontrado ou 0 se não existe. VET tem de estar ordenado pelo campo chave*/
Inteiro: PRI, ULT, MED {primeiro, último e elemento do meio}
POS = 0; // Posicao do elemento nao encontrado
PRI = 1; // Primeiro elemento
ULT = TOTELEM; // Ultimo elemento
Enquanto (PRI < = ULT) e (POS == 0) Faça // Enquanto nao encontrar e nao for fim do vetor
MED = (PRI + ULT)/2 // Calcula o elemento do meio
/*quociente da divisão inteira*/
Se VET[MED] == ELEMPROC Então // Se o elemento do meio for igual ao elemento procurado finaliza
Senão // O elemento procurado deve estar na primeira ou na ultima parte do vetor
Se VET[MED] > ELEMPROC Então // O elemento procurado está na primeira parte do vetor
Senão // O elemento procurado esta na ultima parte do vetor
Se POS > 0 Entao
imprimir "Elemento encontrado na posicao ", pos
Senao
imprimir "Elemento nao encontrado"
Fim-se
Exercício usando pesquisa binária.
Implementar o algoritmo abaixo em um programa em C ou Java.
início /*pesquisa binária*/
inteiro COMEÇO, /*indicador do primeiro elemento da parte do vetor a considerar*/
FIM, /*indicador do último elemento da parte do vetor a considerar*/
MEIO, /*indicador do elemento do meio da parte do vetor Considerada*/
K; /*elemento procurado*/
Até A[MEIO]==K ou COMEÇO >FIM;
imprima (“ Não existe o elemento”);
imprima (“ Está na posição:” , MEIO);