Allidg1 em 21h18min de 1 de dezembro de 2008

2008-12-01T21:18:42Z

Allidg1 em 21h55min de 24 de novembro de 2008

2008-11-24T21:55:26Z

Adolfo: Nova página: A ser editado...

2008-11-19T15:39:36Z

Nova página: A ser editado...

Nova página

A ser editado...

@@ Linha 44: / Linha 44: @@
 ==Referências==
-* http://pt.wikipedia.org/wiki/Busca_Bin%C3%A1ria
-* http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node20.html
+* FEOFILOFF, Paulo. Projeto de Algoritmos: Busca binaria (versao simplificada). Disponível em: <http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html>. Acesso em: 24 nov. 2008
-* http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html
+* RICARTE, Ivan L. M. Busca binária. Disponível em: <http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node20.html>. Acesso em: 24 nov. 2008

← Versão anterior		Edição de 21h55min de 24 de novembro de 2008
Linha 1:		Linha 1:
−	A ~~ser editado~~...	+	[[Image:Busca_Bin%C3%A1ria.jpg\|thumb\|Funcionamento da busca binária para a procura do número 3 no vetor dos números de 1 a 9.\|right\|250px]]
		+
		+	A '''busca binária''' é um [[algoritmo de busca]] em vetores mais eficiente que a [[busca linear]]. Seu funcionamento, porém, é mais complexo.
		+
		+	==Descrição==
		+
		+	A busca binária, primeiramente, nomeia o vetor "0" como sendo o vetor inferior e o vetor "N-1" (N é o número de elementos do vetor) como sendo o vetor superior. A média aritmética entre os números de posição do vetor inferior e do vetor superior dá como resultado a posição do vetor do meio (lembrando que, por serem números inteiros, sua média aritmética retorna um valor também inteiro; por exemplo, se a média for 4,5, o valor retornado é 4). Se o vetor do meio for igual ao número procurado, a busca é cessada e a busca retorna o valor do vetor. Se o vetor do meio não for igual ao número procurado, o programa confere se o vetor procurado é maior ou menor que o atual vetor do meio. Se for menor, o vetor superior é mudado para a posição “meio-1”. Se for maior, o vetor inferior muda para a posição “meio+1”. Assim, é calculada a nova média, que dá a posição do novo vetor do meio. O programa compara novamente este vetor com o do meio, enfim, realizando as mesmas operações citadas anteriormente. Se o programa chegar ao ponto em que as posições inferior e superior se igualam, ele retorna “-1”, o que indica que não existe o número procurado no vetor.
		+
		+	==Implementação em C==
		+	<pre>
		+	#include <stdio.h>
		+	#include <conio.h>
		+
		+	int PesquisaBinaria ( int k[], int chave , int N)
		+	{
		+	int inf,sup,meio;
		+	inf=0;
		+	sup=N-1;
		+	while (inf<=sup)
		+	{
		+	meio=(inf+sup)/2;
		+	if (chave==k[meio])
		+	return meio;
		+	else if (chave<k[meio])
		+	sup=meio-1;
		+	else
		+	inf=meio+1;
		+	}
		+	return -1;
		+	}
		+
		+	int main (){
		+	int c, i, v[9]={1, 2, 3, 4, 5, 6, 7, 8, 9};
		+	printf ("Digite numero procurado: ");
		+	scanf ("%d", &i);
		+	c=PesquisaBinaria (v, i, 9);
		+	if (c==-1)
		+	printf ("O vetor nao contem o numero procurado");
		+	else
		+	printf ("O numero encontra-se no vetor %d", c);
		+	getch();
		+	}
		+	</pre>
		+
		+	==Referências==
		+	* http://pt.wikipedia.org/wiki/Busca_Bin%C3%A1ria
		+	* http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node20.html
		+	* http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html

Busca binária - Histórico de revisão

Allidg1 em 21h18min de 1 de dezembro de 2008

Allidg1 em 21h55min de 24 de novembro de 2008

Adolfo: Nova página: A ser editado...