Revisão de Algoritmos de Busca e Ordenação
---
id: 67f39de5ff88202c94798189
title: Revisão de Algoritmos de Busca e Ordenação
challengeType: 31
dashedName: review-searching-and-sorting-algorithms
---
# --description--
Algoritmos de Busca
Algoritmos de busca permitem que você procure um alvo dentro de uma determinada lista de itens. Em ciência da computação, existem dois algoritmos de busca que você deve conhecer. Eles são algoritmos de busca linear e busca binária. É importante entender as diferenças entre os dois algoritmos e quando usar cada um.Busca Linear
- A busca linear itera por uma lista de itens, verificando cada item desde o início até que o item alvo seja encontrado.
- Se o item alvo for encontrado, o índice onde ele está localizado na lista é retornado.
- Se o alvo não for encontrado, ele retorna
-1, o que significa índice inválido na maioria das linguagens de programação. - Porque a busca linear verifica cada item até encontrar o alvo, ela não é eficiente para uma lista grande de itens.
- A complexidade de tempo da busca linear é
O(n)porque o tempo que leva para percorrer a lista cresce linearmente com o tamanho da lista. - A complexidade de espaço da busca linear é
O(1)porque não requer espaço adicional para percorrer a lista.
Busca Binária
- A busca binária funciona dividindo uma lista de itens ao meio e verificando se o valor alvo está no meio da lista.
- A condição para a busca binária funcionar é que os itens na lista estejam ordenados, seja em ordem crescente ou decrescente.
- A busca binária é um algoritmo mais eficiente para pesquisar em uma grande lista de itens porque divide a lista de itens ao meio e ignora qualquer metade onde o alvo não é encontrado.
- Se o item alvo for encontrado no meio da lista, o índice do item alvo é retornado.
- Se o item não for encontrado, o algoritmo verifica se o item alvo está na metade esquerda ou direita da lista.
- Ele continua a dividir as partes restantes da lista em metades até que o item alvo seja encontrado.
- Se o item alvo finalmente não for encontrado na lista, ele retorna
-1 - A complexidade de tempo da busca binária é
O(log n)porque o tempo que leva para buscar na lista cresce logaritmicamente com o tamanho da lista. - A complexidade de espaço da busca binária é
O(1)porque não requer espaço adicional para percorrer a lista.
Como a Busca Linear Difere da Busca Binária
- A busca binária é mais adequada para uma lista grande de itens em comparação com a busca linear.
- A complexidade de tempo da busca linear é
O(n)porque o tempo que leva para percorrer a lista cresce linearmente com o tamanho da lista. - A complexidade de tempo da busca binária é
O(log n)porque o tempo que leva para buscar na lista cresce logaritmicamente com o tamanho da lista.
Algoritmos de Ordenação e Dividir-e-Conquistar
Em ciência da computação, divide-and-conquer é uma técnica usada para dividir um problema em subproblemas menores para que sejam mais fáceis de resolver. Recursão é a técnica frequentemente empregada em divide-and-conquer e divide-and-conquer é uma estratégia poderosa usada para implementar muitos algoritmos de ordenação eficientes como merge sort.Ordenação por Merge
- Merge sort é um algoritmo de ordenação que segue a abordagem de dividir e conquistar.
- Funciona dividindo recursivamente uma lista em sublistas menores até que cada sublista contenha apenas um elemento.
- Em seguida, ele mescla repetidamente as sublistas de volta em uma ordem ordenada.
- A complexidade de tempo do merge sort é
O(n log n)porque a lista é continuamente dividida ao meio(log n)e depois mesclada(O(n)). - A complexidade de espaço do merge sort é
O(n)porque ele não é um algoritmo de ordenação in-place.