PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO - ATIVIDADE 1

Prévia do material em texto

Uma busca binária começará examinando o item do meio. Se esse item for aquele que estamos procurando, a busca termina. Se não for o item correto, podemos usar a natureza ordenada da lista para eliminar a metade dos itens restantes.
A busca sequencial é o algoritmo mais simples de busca:
· Percorra todo o vetor comparando a chave com o valor de cada
posição.
· Se for igual para alguma posição, então devolva esta posição.
· Se o vetor todo foi percorrido então devolva -1.
A busca binária é um algoritmo um pouco mais sofisticado.  E mais eficiente, mas requer que o vetor esteja ordenado pelos valores  da chave de busca.
Antes de tudo devemos recapitular o que uma busca/pesquisa faz, nada 
mais que verificar a presença ou não de um elemento em um conjunto de 
dados que essa busca queira achar. O que diferencia é a forma de como essa 
pesquisa será feita, no nosso caso de estudo é a busca Binária e a Sequencial.
A Busca Sequencial é a forma mais simples de se fazer uma pesquisa, a
partir do momento que se tem um vetor com suas informações preenchidas, o 
algoritmo de busca percorre índice por índice procurando e comparando o 
conteúdo o qual quer achar. A cada índice que é percorrido tem-se um retorno 
"sucesso" ou "insucesso".
Aqui temos um exemplo de algoritmo de Busca Sequencial em um vetor 
não ordenado:
 int busca(int a[], int indice, int esq, int dir){
 for(int i=esq; i<=dir;i++)
 if(indice==a[i] return i;)
 return -1;
 
Antes de tudo devemos recapitular o que uma busca/pesquisa faz, nada 
mais que verificar a presença ou não de um elemento em um conjunto de 
dados que essa busca queira achar. O que diferencia é a forma de como essa 
pesquisa será feita, no nosso caso de estudo é a busca Binária e a Sequencial.
A Busca Sequencial é a forma mais simples de se fazer uma pesquisa, a
partir do momento que se tem um vetor com suas informações preenchidas, o 
algoritmo de busca percorre índice por índice procurando e comparando o 
conteúdo o qual quer achar. A cada índice que é percorrido tem-se um retorno 
"sucesso" ou "insucesso".
Aqui temos um exemplo de algoritmo de Busca Sequencial em um vetor 
não ordenado:
 int busca(int a[], int indice, int esq, int dir){
 for(int i=esq; i<=dir;i++)
 if(indice==a[i] return i;)
 return -1;
 
Antes de tudo devemos recapitular o que uma busca/pesquisa faz, nada 
mais que verificar a presença ou não de um elemento em um conjunto de 
dados que essa busca queira achar. O que diferencia é a forma de como essa 
pesquisa será feita, no nosso caso de estudo é a busca Binária e a Sequencial.
A Busca Sequencial é a forma mais simples de se fazer uma pesquisa, a
partir do momento que se tem um vetor com suas informações preenchidas, o 
algoritmo de busca percorre índice por índice procurando e comparando o 
conteúdo o qual quer achar. A cada índice que é percorrido tem-se um retorno 
"sucesso" ou "insucesso".
Aqui temos um exemplo de algoritmo de Busca Sequencial em um vetor 
não ordenado:
 int busca(int a[], int indice, int esq, int dir){
 for(int i=esq; i<=dir;i++)
 if(indice==a[i] return i;)
 return -1;
 
A busca sequencial é a forma mais simples de fazer uma pesquisa, a partir do momento que se tem um vetor com as suas informações preenchidas, o algoritmo de busca percorre índice a índice procurando e comparando o conteúdo em que está sendo pesquisado. A cada índice tem um retorno do algoritmo “sucesso” ou “insucesso”. Segue o exemplo de um vetor de busca sequencial não ordenado: int busca (int a [], int índice, int esq, int dir) {
For (int i-=esq; i<=dir; i++)
If (índice==a [i] return i;)
Return -1;
}
Na busca binária é um método mais complexo e o vetor precisa estar ordenado, ao contrário do vetor sequencial que tanto faz se ele estiver ordenado ou não. Funciona da seguinte maneira: precisa realizar a comparação do meio do vetor, caso encontre o dado a pesquisa retorna com sucesso. Se a chave for menor, o procedimento é repetido na primeira metade do vetor, se a chave for maior, o procedimento é repetido na segunda metade do vetor. O processo é repetido até que seja encontrando o dado desejado retornando com sucesso ou que acabe os itens do vetor.
Segue o exemplo de um vetor de busca binária: int binaria (int a[], int índice, int esq, int dir) {
while (dir>=esq)}
int meio = (esq+dir)/2;
if (indice== a[meio]) return meio;
if (índice<a[meio])
dir=meio -1;
else esq =meio +1;
}
return -1;
}
A busca sequencial é a forma mais simples de fazer uma pesquisa, a partir do momento que se tem um vetor com as suas informações preenchidas, o algoritmo de busca percorre índice a índice procurando e comparando o conteúdo em que está sendo pesquisado. A cada índice tem um retorno do algoritmo “sucesso” ou “insucesso”. Segue o exemplo de um vetor de busca sequencial não ordenado: 
int busca (int a [], int índice, int esq, int dir) {
For (int i-=esq; i<=dir; i++)
If (índice==a [i] return i;)
Return -1;
}
Na busca binária é um método mais complexo e o vetor precisa estar ordenado, ao contrário do vetor sequencial que tanto faz se ele estiver ordenado ou não. Funciona da seguinte maneira: precisa realizar a comparação do meio do vetor, caso encontre o dado a pesquisa retorna com sucesso. Se a chave for menor, o procedimento é repetido na primeira metade do vetor, se a chave for maior, o procedimento é repetido na segunda metade do vetor. O processo é repetido até que seja encontrando o dado desejado retornando com sucesso ou que acabe os itens do vetor.
Segue o exemplo de um vetor de busca binária: 
int binaria (int a[], int índice, int esq, int dir) {
while (dir>=esq)}
int meio = (esq+dir)/2;
if (indice== a[meio]) return meio;
if (índice<a[meio])
dir=meio -1;
else esq =meio +1;
}
return -1;
}