Se você é novo em programação ou pensamento algorítmico, dois algoritmos principais para aprender são pesquisa binária e classificação rápida. Esses algoritmos são amplamente utilizados na ciência da computação e têm muitas aplicações no mundo real.

Neste artigo, fornecerei um guia detalhado para pesquisa binária e classificação rápida, incluindo suas implementações, casos de uso e aplicativos do mundo real. Também fornecerei exemplos e explicações para ajudá-lo a entender esses algoritmos e como eles funcionam.

Portanto, seja você um iniciante ou um programador experiente, continue lendo para saber mais sobre esses poderosos algoritmos e como eles podem ajudá-lo a resolver problemas em seu código e no mundo real.

Se você quiser aprender mais sobre algoritmos, leia o livro “Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People” de Aditya Bhargava .

Pesquisa binária

A busca binária é um algoritmo de busca que divide repetidamente o intervalo de busca pela metade, eliminando metade dos elementos restantes em cada etapa. Essa abordagem resulta em uma complexidade de tempo logarítmica de O(log n). A pesquisa binária é amplamente usada em muitas aplicações, incluindo pesquisa em bancos de dados, localização de itens específicos em programas de computador e localização de valores em conjuntos de dados numéricos.

Implementação

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Para encontrar o índice de 7in [1, 2, 3, 4, 5, 6, 7, 8, 9], compare-o com o elemento do meio, 5. Se for maior que 5, procure na metade superior [6, 7, 8, 9]. Se for menor que 8, procure na metade inferior [1, 2, 3, 4, 5, 6]. Depois de encontrar 7, seu índice é 6.

Casos de uso

1. Procurando por um elemento em uma lista ordenada ou encontrando o índice de um elemento em uma lista ordenada: A busca binária pode executar ambas as tarefas em O(log n)complexidade de tempo.
2. Localizando o elemento em uma lista classificada mais próxima de um determinado valor: Use a pesquisa binária para localizar o elemento que é igual ao valor fornecido ou logo antes ou depois dele.
3. Encontrar um elemento de pico em uma matriz classificada em ordem crescente e decrescente: Use a pesquisa binária para encontrar o elemento de pico, que é maior que seus vizinhos.

1. A pesquisa binária pesquisa com eficiência grandes bancos de dados, como páginas da Web e registros médicos, para retornar resultados relevantes aos usuários.
2. O algoritmo é usado em redes de computadores para localizar rapidamente um determinado pacote de dados em uma ordem classificada de pacotes de dados de rede e no comércio financeiro para tomar decisões informadas com base em dados específicos em grandes conjuntos de dados.
3. A pesquisa binária também é usada no aprendizado de máquina para encontrar hiperparâmetros ideais para um determinado modelo e no sequenciamento de DNA para identificar genes específicos ou mutações em grandes conjuntos de dados.

O Quick Sort é um algoritmo de classificação amplamente usado que classifica eficientemente uma matriz particionando-a recursivamente em duas submatrizes. O algoritmo seleciona um elemento pivô da matriz e divide os elementos restantes em dois grupos: os menores ou iguais ao pivô e os maiores que o pivô. Em seguida, ele classifica recursivamente os dois grupos até que todo o array esteja classificado. O Quick Sort é um dos algoritmos de classificação mais rápidos devido à sua estratégia de dividir e conquistar, com uma complexidade média de tempo de O(n log n). Ele pode lidar com grandes conjuntos de dados e é comumente usado em vários aplicativos.

Implementação

def quick_sort(arr):
    if len(arr) <= 1:
        return arrp
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x <= pivot]
        right = [x for x in arr[1:] if x > pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

Suponha que temos um array com os seguintes elementos: [9, 7, 5, 11, 12, 2, 14, 3, 10, 6].

Para classificar a matriz usando o algoritmo Quick Sort, siga estas etapas:

1. Escolha o primeiro elemento da matriz como o elemento pivô, neste caso 9.
2. Particione a matriz em duas submatrizes: uma submatriz com elementos menores ou iguais ao pivô e a outra submatriz com elementos maiores que o pivô.

[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
 ^ pivot
[7, 5, 2, 3, 6]   [9]   [11, 12, 14, 10]

[7, 5, 2, 3, 6]
 ^ pivot
[5, 2, 3, 6]   [7]
 ^ pivot
[2, 3]   [5]   [6]   [7]
 ^ pivot
[2]   [3]   [5]   [6]   [7]
[2, 3, 5, 6, 7]

[11, 12, 14, 10]
 ^ pivot
[10]   [11]   [12, 14]
               ^ pivot
[10]   [11]   [12]   [14]
[10, 11, 12, 14]

[2, 3, 5, 6, 7]   [9]   [10, 11, 12, 14]
[2, 3, 5, 6, 7, 9, 10, 11, 12, 14]

3. Quick Sort é um algoritmo clássico de divisão e conquista usado na educação e programação de ciência da computação.
4. O Quick Sort é útil em aplicativos onde o uso de memória é uma preocupação, como sistemas embarcados e aplicativos em tempo real.

1. Quick Sort é comumente usado em bancos de dados e linguagens de programação para classificar grandes conjuntos de dados e estruturas de dados.
2. O Quick Sort é usado em computação científica e análise numérica para classificar grandes conjuntos de dados gerados em simulações e experimentos.
3. A classificação rápida é útil no comércio eletrônico para classificar rapidamente produtos, avaliações e outros dados com base na preferência do usuário. É útil para varejistas online com grandes catálogos.

Pesquisa binária e classificação rápida são dois algoritmos fundamentais que todo programador deve conhecer. A pesquisa binária é um algoritmo de pesquisa que ajuda a encontrar itens específicos em programas de computador, enquanto a classificação rápida é um algoritmo de classificação que pode classificar com eficiência grandes conjuntos de dados. Ambos os algoritmos têm inúmeras aplicações no mundo real, desde pesquisa em bancos de dados e negociação financeira até aprendizado de máquina e sequenciamento de DNA. Neste artigo, forneço um guia detalhado para ambos os algoritmos, incluindo suas implementações, casos de uso e aplicativos do mundo real. Seja você um iniciante ou um programador experiente, esses poderosos algoritmos podem ajudá-lo a resolver problemas em seu código e no mundo real. Se você quiser aprender mais sobre algoritmos, você pode querer ler o livro“Grokking Algorithms: Um guia ilustrado para programadores e outras pessoas curiosas” por Aditya Bhargava .

No próximo artigo, abordarei outro algoritmo popular: BFS (Breadth-First Search). Este algoritmo é usado para explorar todos os vértices de um grafo.