Baixe o app para aproveitar ainda mais
Prévia do material em texto
Antes de mais nada, devemos recapitular o que uma busca/pesquisa faz, em sumo 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 como essa pesquisa será feita, nesse caso dos nossos estudos será a busca Binária eSequencial. No caso da busca Binária é um método mais complexo e tem a exigência que o vetor esteja ordenado, é um algoritmo um pouco mais sofisticado e mais eficiente, mas requer que o vetor esteja ordenado pelos valores da chave de busca, ao contrário da busca Sequencial que tanto faz se é ordenado ou não. Antes de mais nada, devemos recapitular o que uma busca/pesquisa faz, em sumo 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 como essa pesquisa será feita, nesse caso dos nossos estudos será a busca Binária e Sequencial. No caso da busca Binária é um método mais complexo e tem a exigência que o vetor esteja ordenado, é um algoritmo um pouco mais sofisticado e mais eficiente, mas requer que o vetor esteja ordenado pelos valores da chave de busca, ao contrário da busca Sequencial que tanto faz se é ordenado ou não. O primeiro passo da busca Binária começará por examinar o item do meio, caso ache o dado procurado a pesquisa retornada com sucesso, caso contrário; Segundo passo é que 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. Assim o processo é repetido até que seja retornado com sucesso ou que acabe os itens do vetor. · primeiro passo da busca Binária começará por examinar o item do meio, caso ache o dado procurado a pesquisa retornada com sucesso, caso contrário; · Segundo passo é que 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. Assim o processo é repetido até que seja retornado com sucesso ou que acabe os itens do vetor. Abaixo um exemplo de algoritmo de busca binária: int binaria(int a[], int indice, int esq, int dir){ while(dir>=esq){ int meio=(esq+dir)/2; if(indice==a[meio]) return meio; if(indice<a[meio]) dir=meio-1; } } 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 de “sucesso” ou “insucesso”. Em linhas gerais, 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 Abaixo 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; }
Compartilhar