nem mesmo um único passe de dia, quando não temos que procurar por algo em nosso dia-a-dia, chaves de carro, livros, caneta, carregador móvel e o que não. O mesmo é a vida de um computador, há tantos dados armazenados nele, que sempre que um usuário pede alguns dados, o computador tem que pesquisar sua memória para procurar os dados e torná-lo disponível para o usuário. E o computador tem suas próprias técnicas para pesquisar através de sua memória rápida, que você pode aprender mais sobre em nossa série de tutoriais do Sistema Operacional.
e se você tiver que escrever um programa para pesquisar um dado número em um array? Como vais fazer isso?
Bem, a busca de um elemento em uma determinada matriz, existem dois algoritmos populares disponíveis:
- Pesquisa Linear
- Pesquisa Binária
Pesquisa Linear
pesquisa Linear é muito básico e simples algoritmo de pesquisa. Em busca Linear, buscamos um elemento ou valor em uma determinada matriz atravessando a matriz desde o início, até que o elemento ou valor desejado seja encontrado.
compara-se o elemento a ser procurado com todos os elementos presentes na matriz e quando o elemento é comparado com sucesso, ele retorna o índice do elemento na matriz, então ele voltar -1.
a pesquisa Linear é aplicada em listas não triadas ou não ordenadas, quando há menos elementos em uma lista.
Features of Linear Search Algorithm
- It is used for unsorted and unordered small list of elements.
- tem uma complexidade de tempo de O( n), o que significa que o tempo é linearmente dependente do número de elementos, o que não é ruim, mas não tão bom também.
- tem uma implementação muito simples.
iremos implementar o algoritmo de pesquisa Linear no próximo tutorial.
busca binária
busca binária é usada com matriz ou lista ordenada. Na busca binária, seguimos os seguintes passos:
- começamos por comparar o elemento a ser pesquisado com o elemento no meio da lista/array.Se obtivermos uma correspondência, devolvemos o índice do elemento médio.
- se não obtivermos uma correspondência, verificamos se o elemento a ser pesquisado é menor ou maior do que o valor do elemento médio.
- Se o elemento/número a ser pesquisado é de maior valor do que o número meio, em seguida, escolhemos os elementos do lado direito do elemento intermediário(como a lista/matriz é classificada, portanto, no direito, temos todos os números maiores que o número meio), e comece novamente a partir do passo 1.
- se o elemento / número a ser pesquisado for menor em valor do que o número do meio, então nós pegamos os elementos do lado esquerdo do elemento do meio, e começamos novamente a partir do Passo 1.
a busca binária é útil quando há um grande número de elementos em uma matriz e eles são ordenados.
então uma condição necessária para a pesquisa binária funcionar é que a lista/array deve ser ordenada.
características da pesquisa binária
- é ótimo para pesquisar através de grandes matrizes ordenadas.
- tem uma complexidade de tempo de O (log n) que é uma complexidade de tempo muito boa. Vamos discutir isso em detalhes no tutorial de busca binária.
- tem uma implementação simples.