Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Pesquisa Linear]
[Patrick Schmid, da Universidade de Harvard]
[Esta é CS50.] [CS50.TV]
Procurando é algo que você provavelmente fazer mais vezes do que você pensa.
Obviamente, cada vez que você abrir um navegador
e busca de uma página web -
ou busca de seus amigos em seu site de rede social -
você está procurando.
Mas isso é apenas uma pequena parte da pesquisa que você faz em uma base diária.
Quando você quer encontrar essa camisa um azul no armário,
ou blusa que vermelha perfeita para a ocasião,
você está procurando.
Quando você vai a uma loja que você nunca esteve antes,
e você está olhando para o brócolis no corredor do produto
você está procurando.
O que você pode ter começado a notar
é que, dependendo do que você está procurando
ou como os itens são organizados quando você está olhando para eles
ele tem um efeito sobre como você busca.
Por exemplo, se suas camisas estão penduradas no armário,
você pode provavelmente apenas pegá-lo sem muita procura.
Se você está assumindo que você tem que caminhar até o altar
para obter o brócolis, provavelmente você tem que olhar para todos os outros vegetais
antes de você achar que o brócolis.
Pesquisa linear é um exemplo de um método de pesquisa de tais - ou algoritmo.
Como o nome indica,
este método de pesquisa para um item de uma forma linear, uma após a outra.
Então, quando você está olhando para os resultados do seu motor de busca favorito
e que você lê a lista de resultados,
você está usando busca linear.
Okay. Vejamos um exemplo.
Dizer que temos uma lista de números - 2, 4, 0, 5, 3, 7, 8, e 1 -
e nós estamos olhando para o número 0.
Obviamente, você pode apenas ver que a 0 está na terceira posição.
Mas, um programa de computador não é que a sorte.
Só pode "ver" a um número de cada vez.
Assim, a partir do início da lista,
ele só "vê" o 2.
O programa verifica então - é igual a 2 0?
Obviamente que não. Por isso, vai para o próximo número, 4.
Faz 4 0 iguais? Nope.
O próximo, 0. Ah! Zero é igual a 0.
Não temos isso! É na terceira posição.
Okay. Vejamos alguns pseudocódigo.
É apenas um par de linhas longas, mas vamos olhar para ele uma linha de cada vez.
Primeiro, vamos definir a função - e nós vamos chamá-lo de busca linear -
e leva dois argumentos - chave e matriz.
A chave é que o valor que estamos procurando,
portanto, no exemplo anterior, que foi a zero.
Uma matriz é uma lista de números
que tem todos os valores que nós vamos buscar.
Então, o que nós queremos fazer é que nós queremos olhar -
a partir de todas as posições, assim começando no início da matriz
até o fim da matriz - de modo que o comprimento da matriz -
olhar para cada posição única e verificar cada uma.
Então é isso que que "para" loop está fazendo.
E em cada posição, vamos dizer
"É que o valor em que a actual posição igual à chave que estamos procurando?"
Assim - no exemplo anterior novamente, a tecla foi de 0 -
por isso estamos dizendo que "é a matriz na posição i igual a zero?"
Se for, vamos voltar 'i' porque essa é a posição atual estamos.
Assim, no exemplo anterior,
que foi a terceira posição.
Se já passou por toda a matriz
e não encontramos nada -
então vamos dizer que estávamos procurando para o número 500
o que claramente não estava naquele exemplo -
temos que retornar algo,
e nós estamos indo para retornar -1.
E estamos apenas retornando -1 porque é uma posição
que não existe na matriz.
E o que significa que quando você recebe de volta de uma função
ele diz que "Hmm, tudo bem. Acho que não encontrou nada.
Para que nunca 500 estava lá. "
A coisa agradável sobre a busca linear é que
ele vai trabalhar em qualquer lista de itens,
independentemente da forma como os itens são ordenados.
Não importa onde o brócolis é no corredor do produto.
Enquanto você anda pelo corredor, desde o início até o fim,
você é obrigado a encontrá-lo,
assumindo que a loja não está sem brócolis, é claro.
Mas é a maior força é também sua maior fraqueza.
Digamos que você tem uma lista de 200 números
que estão ordenados de 1 a 200.
Se você está procurando para o número 198,
você tem que procurar quase toda a lista de números
antes de encontrar o que você está procurando.
Deve haver uma maneira melhor!
Tenha certeza de que existe.
Mas, isso é assunto para outro vídeo.
Além disso, não se preocupe!
Só porque busca linear não é a melhor solução em todas as situações,
isso não significa que ele não vem a calhar.
Caso contrário, como você achar que o brócolis no corredor do produto?
Meu nome é Patrick Schmid, e este é o CS50.
[CS50.TV]