[Powered by Google Translate] [Busca lineal]
[Patrick Schmid, da Universidade de Harvard]
[Esta é CS50.] [CS50.TV]
Buscar é algo que probablemente facer máis veces do que pensa.
Obviamente, cada vez que abrir un navegador
e busca dunha páxina web -
ou procura dos seus amigos no seu sitio web de redes sociais -
está a procurar.
Pero isto é só unha pequena parte da investigación que fai nunha base diaria.
Cando quere atopar esa camisa dun azul no armario,
ou blusa que vermella perfecta para a ocasión,
está a procurar.
Cando vai a unha tenda que nunca estivo antes,
e está mirando para o brócolis no corredor do produto
está a procurar.
O que podes comezar a notar
é que, dependendo do que está a buscar
ou como os elementos son organizados cando está mirando para eles
ten un efecto sobre como buscar.
Por exemplo, se as súas camisas están colgadas no armario,
pode ser só pegalo sen moita demanda.
Se está asumindo que ten que camiñar ata o altar
para obter o brócolis, probabelmente vostede ten que ollar para os outros vexetais
antes de pensar que o brócolis.
Busca lineal é un exemplo dun método de investigación de tales - ou algoritmo.
Como o nome indica,
Este método de investigación para un elemento dunha forma lineal, unha despois da outra.
Entón, cando está mirando para os resultados do seu motor de procura favorito
e que le a lista de resultados,
está a usar procura lineal.
Okay. Vexamos un exemplo.
Dicir que temos unha lista de números - 2, 4, 0, 5, 3, 7, 8, e 1 -
e nós estamos mirando para o número 0.
Obviamente, pode só ver que a 0 está na terceira posición.
Pero, un programa de ordenador non é que a sorte.
Só pode "ver" a un número cada vez.
Así, a partir do inicio da lista,
el só "ve" o 2.
O programa comproba entón - é igual a 2 0?
Obviamente que non. Por iso, vai ao seguinte número 4.
Fai 4 0 iguais? Nope.
O seguinte, 0. Ah! Cero é igual a 0.
Non temos iso! É na terceira posición.
Okay. Vexamos algúns pseudocódigo.
É só un par de liñas longas, pero imos ollar para el unha liña de cada vez.
En primeiro lugar, imos definir a función - e nós imos chamalo de procura lineal -
e leva dous argumentos - chave e matriz.
A clave é que o valor que estamos a buscar,
polo tanto, no exemplo anterior, que foi a cero.
Unha matriz é unha lista de números
que ten todos os valores que nós imos buscar.
Entón, o que queremos facer é que queremos ollar -
a partir de todas as posicións, así comezando no inicio da matriz
ata o fin da matriz - de xeito que a lonxitude da matriz -
mirar para cada posición única e comprobar cada unha.
Entón é iso que que "a" loop está facendo.
E en cada posición, imos dicir
"É que o valor en que a actual posición igual á clave que estamos a buscar?"
Así - no exemplo anterior de novo a tecla foi de 0 -
por iso estamos dicindo que "é a matriz na posición i igual a cero?"
Se for, imos voltar 'i' porque esa é a posición actual estamos.
Así, no exemplo anterior,
que foi a terceira posición.
Se xa pasou por toda a matriz
e non atopamos nada -
entón imos dicir que estabamos a buscar ao número 500
o que claramente non estaba naquel exemplo -
temos que volver algo,
e nós estamos indo para voltar -1.
E estamos só retornando -1 porque é unha posición
que non existe na matriz.
E o que significa que cando recibe de volta dunha función
el di que "Hmm, todo ben. Creo que non atopou nada.
Para que nunca 500 estaba alí. "
O agradable sobre a procura lineal é que
vai traballar en calquera lista de elementos,
independentemente da forma na que os elementos son ordenados.
Non importa onde o brócolis é no corredor do produto.
Mentres anda polo corredor, desde o principio ata o final,
vostede está obrigado a atopalo,
asumindo que a tenda non está sen brócolis, por suposto.
Pero é a maior forza é tamén a súa maior debilidade.
Digamos que ten unha lista de 200 números
que están ordenados de 1 a 200.
Se está a buscar para o número 198,
ten que buscar case toda a lista de números
antes de atopar o que está a procurar.
Debe haber un xeito mellor!
Asegúrese de que existe.
Pero, iso é asunto para outro vídeo.
Ademais, non se preocupe!
Só porque busca lineal non é a mellor solución en todas as situacións,
iso non significa que non vén a cadra.
Se non, como cre que o brócolis no corredor do produto?
O meu nome é Patrick Schmid, e este é o CS50.
[CS50.TV]