Revisão de Algoritmos de Busca e Ordenação
---
id: 6995c850f4445187be2a1c2f
title: Revisão de Algoritmos de Busca e Ordenação
challengeType: 31
dashedName: review-searching-and-sorting-algorithms-js
---
# --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 um array de items, 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 no array é retornado.
- Se o alvo não for encontrado, ele retorna
-1, o que significa índice inválido em JavaScript. - Como a busca linear verifica cada item até encontrar o alvo, ela não é eficiente para um array grande de itens.
- A complexidade de tempo da busca linear é
O(n)porque o tempo que leva para buscar no array cresce linearmente com o tamanho do array. - A complexidade de espaço da busca linear é
O(1)porque não requer nenhum espaço adicional para buscar no array.
Busca Binária
- A busca binária funciona dividindo um array de items ao meio e verificando se o valor alvo está no meio do array.
- A condição para a busca binária funcionar é que os items no array devem estar ordenados, seja em ordem crescente ou decrescente.
- A busca binária é um algoritmo mais eficiente para buscar em um grande array de items porque divide o array ao meio e ignora qualquer metade onde o alvo não é encontrado.
- Se o item alvo for encontrado no meio do array, o índice do item alvo será retornado.
- Se o item não for encontrado, o algoritmo verifica se o item alvo está na metade esquerda ou direita do array.
- Ele continua a dividir as partes restantes do array em metades até que o item alvo seja encontrado.
- Se o item alvo não for encontrado no array, ele retorna
-1, - A complexidade de tempo da busca binária é
O(log n)porque o tempo que leva para buscar no array cresce logaritmicamente com o tamanho do array. - A complexidade de espaço da busca binária é
O(1)porque não requer nenhum espaço adicional para buscar no array.
Como a Busca Linear Difere da Busca Binária
- A busca binária é mais adequada para um grande
arraydeitemsem comparação com a busca linear. - A complexidade de tempo da busca linear é
O(n)porque o tempo que leva para buscar no array cresce linearmente com o tamanho do array. - A complexidade de tempo da busca binária é
O(log n)porque o tempo que leva para buscar no array cresce logaritmicamente com o tamanho do array.
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 um array em subarrays menores até que cada subarray contenha apenas um elemento.
- Em seguida, ele mescla repetidamente os subarrays de volta em uma ordem ordenada.
- A complexidade de tempo para merge sort é
O(n log n)porque o array é continuamente dividido ao meio(log n)e então mesclado(O(n)). - A complexidade de espaço do merge sort é
O(n)porque ele não é um algoritmo de ordenação in-place.