[Música tocando] DOUG LLOYD: Linear pesquisa é um algoritmo que pode usar para encontrar um elemento em uma matriz. Uma recordação algoritmo é um conjunto passo-a-passo de instruções para completar uma tarefa. 

A pesquisa linear algoritmo funciona da seguinte maneira. Iterar através da matriz da esquerda para a direita, à procura de um elemento especificado. 

Em pseudocódigo, que é uma forma mais versão destilada desta frase, Se o primeiro elemento de que é você está procurando, você pode parar. Caso contrário, passar para o próximo elemento e manter indo mais e mais até que você encontre o elemento, ou você não faz. Assim, podemos usar o linear algoritmo de busca, por exemplo, para encontrar o valor alvo nove nessa matriz. Bem vamos começar pelo começo. Se é o que nós somos procurando, nós podemos parar. Não é, não estamos procurando 11. Assim, caso contrário, passar para o próximo elemento. 

Então olhamos para 23. 23 é o que estamos procurando? Bem, não, por isso, passar para a próxima elemento eo elemento seguinte, e continuamos a atravessar este processo mais e mais e mais, até que pousar em uma situação como esta. 

Nove é o que estamos procurando, e este elemento da matriz é, de valor é nove. E assim nós encontramos o que nós somos procurando, e nós podemos parar. A pesquisa linear tem concluído, com sucesso. 

Mas o que dizer se estamos procurando um elemento que não está em nossa matriz. Será que busca linear ainda funciona? Bem certeza. Então, nós repetimos este processo começando no primeiro elemento. Se é o que nós somos procurando, nós podemos parar. Não é. Caso contrário, nós nos movemos para o próximo elemento. 

Mas podemos continuar a repetir esse processo, examina cada elemento, por sua vez, na esperança de que nós encontramos o número 50. Mas nós não saberemos se nós encontramos o número 50 ou se nós não o fez, até que nós já pisou sobre cada elemento da matriz. 

Apenas uma vez que fizemos isso e vir acima do short, podemos concluir que 50 não se encontra na matriz. E assim a busca linear algoritmo, bem ele falhou, per se. Mas não no sentido de que ele não teve sucesso em fazer o que pedimos que ele faça. 

Ele teve sucesso em como tanto como ele não encontrou 50, mas 50 não estava na matriz. Mas temos exaustivamente pesquisados através de cada elemento e assim, enquanto não encontramos qualquer coisa, pesquisa linear ainda sucede mesmo que a elemento não está na matriz. 

Então, qual é o pior caso cenário com busca linear? Bem, temos de olhar através de cada elemento, quer porque o elemento alvo é o último elemento da matriz, ou o elemento que estamos procurando não realmente existem na matriz em tudo. Qual é o melhor cenário? Bem que poderíamos encontrar o elemento imediatamente. E quantos elementos nós então temos que olhar na na melhor das hipóteses, se nós estamos olhando para ele e nós encontrá-lo logo no início? Nós podemos parar imediatamente. 

O que isso diz sobre a complexidade da busca linear? Bem, no pior caso, temos olhar para cada elemento. E assim ele é executado em O de N, no pior dos casos. 

Na melhor das hipóteses, nós vamos encontrar o elemento imediatamente. E assim é executado em omega de 1. 

Eu sou Doug Lloyd. Este é CS50.