Jeśli jesteś nowy w programowaniu lub myśleniu algorytmicznym, dwa kluczowe algorytmy do nauczenia to wyszukiwanie binarne i szybkie sortowanie. Algorytmy te są szeroko stosowane w informatyce i mają wiele zastosowań w świecie rzeczywistym.

W tym artykule przedstawię szczegółowy przewodnik po wyszukiwaniu binarnym i szybkim sortowaniu, w tym ich implementacje, przypadki użycia i rzeczywiste zastosowania. Podam również przykłady i wyjaśnienia, które pomogą Ci zrozumieć te algorytmy i sposób ich działania.

Niezależnie od tego, czy jesteś początkującym, czy doświadczonym programistą, czytaj dalej, aby dowiedzieć się więcej o tych potężnych algorytmach i o tym, jak mogą one pomóc w rozwiązywaniu problemów w kodzie iw świecie rzeczywistym.

Jeśli chcesz dowiedzieć się więcej o algorytmach, możesz przeczytać książkę „Grokking Algorithms: Ilustrowany przewodnik dla programistów i innych ciekawskich” autorstwa Adityi Bhargavy .

Wyszukiwanie binarne

Wyszukiwanie binarne to algorytm wyszukiwania, który wielokrotnie dzieli interwał wyszukiwania na pół, eliminując połowę pozostałych elementów na każdym kroku. Takie podejście skutkuje logarytmiczną złożonością czasową O(log n). Wyszukiwanie binarne jest szeroko stosowane w wielu zastosowaniach, w tym w przeszukiwaniu baz danych, znajdowaniu określonych elementów w programach komputerowych i lokalizowaniu wartości w zestawach danych liczbowych.

Realizacja

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

Aby znaleźć indeks 7in [1, 2, 3, 4, 5, 6, 7, 8, 9], porównaj go ze środkowym elementem, 5. Jeśli jest większa niż 5, szukaj w górnej połowie [6, 7, 8, 9]. Jeśli jest mniejsza niż 8, szukaj w dolnej połowie [1, 2, 3, 4, 5, 6]. Po znalezieniu 7jego indeks to 6.

Przypadków użycia

1. Wyszukiwanie elementu na posortowanej liście lub znajdowanie indeksu elementu na posortowanej liście: Wyszukiwanie binarne może wykonywać oba zadania ze O(log n)złożonością czasową.
2. Znajdowanie elementu na posortowanej liście najbliższego podanej wartości: Użyj wyszukiwania binarnego, aby znaleźć element równy podanej wartości lub tuż przed nim lub po nim.
3. Znajdowanie elementu szczytowego w tablicy posortowanej w porządku rosnącym, a następnie malejącym: Użyj wyszukiwania binarnego, aby znaleźć element szczytowy, który jest większy niż jego sąsiedzi.

1. Wyszukiwanie binarne skutecznie przeszukuje duże bazy danych, takie jak strony internetowe i dokumentacja medyczna, aby zwrócić użytkownikom odpowiednie wyniki.
2. Algorytm jest używany w sieciach komputerowych do szybkiego zlokalizowania określonego pakietu danych w posortowanej kolejności pakietów danych sieciowych oraz w handlu finansowym do podejmowania świadomych decyzji na podstawie określonych danych w dużych zbiorach danych.
3. Wyszukiwanie binarne jest również wykorzystywane w uczeniu maszynowym do znajdowania optymalnych hiperparametrów dla danego modelu oraz w sekwencjonowaniu DNA do identyfikacji określonych genów lub mutacji w dużych zbiorach danych.

Szybkie sortowanie to szeroko stosowany algorytm sortowania, który wydajnie sortuje tablicę, rekurencyjnie dzieląc ją na dwie podtablice. Algorytm wybiera element obrotowy z tablicy i dzieli pozostałe elementy na dwie grupy: mniejsze lub równe obrotowi i większe od obrotu. Następnie rekurencyjnie sortuje dwie grupy, aż cała tablica zostanie posortowana. Szybkie sortowanie jest jednym z najszybszych algorytmów sortowania ze względu na strategię dziel i zwyciężaj, ze średnią złożonością czasową O(n log n). Może obsługiwać duże zbiory danych i jest powszechnie używany w różnych aplikacjach.

Realizacja

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)

Załóżmy, że mamy tablicę z następującymi elementami: [9, 7, 5, 11, 12, 2, 14, 3, 10, 6].

Aby posortować tablicę przy użyciu algorytmu szybkiego sortowania, wykonaj następujące kroki:

1. Wybierz pierwszy element tablicy jako element przestawny, w tym przypadku 9.
2. Podziel tablicę na dwie podtablice: jedną podtablicę z elementami mniejszymi lub równymi osi obrotu, a drugą podtablicę z elementami większymi niż wartość obrotu.

[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. Szybkie sortowanie to klasyczny algorytm typu „dziel i zwyciężaj” stosowany w nauczaniu informatyki i programowaniu.
4. Szybkie sortowanie jest przydatne w aplikacjach, w których zużycie pamięci stanowi problem, takich jak systemy wbudowane i aplikacje działające w czasie rzeczywistym.

1. Szybkie sortowanie jest powszechnie stosowane w bazach danych i językach programowania do sortowania dużych zbiorów danych i struktur danych.
2. Szybkie sortowanie jest wykorzystywane w obliczeniach naukowych i analizach numerycznych do sortowania dużych zbiorów danych generowanych w symulacjach i eksperymentach.
3. Szybkie sortowanie jest przydatne w handlu elektronicznym do szybkiego sortowania produktów, recenzji i innych danych na podstawie preferencji użytkownika. Jest to przydatne dla sprzedawców internetowych z dużymi katalogami.

Wyszukiwanie binarne i szybkie sortowanie to dwa podstawowe algorytmy, które powinien znać każdy programista. Wyszukiwanie binarne to algorytm wyszukiwania, który pomaga znaleźć określone elementy w programach komputerowych, podczas gdy szybkie sortowanie to algorytm sortowania, który może wydajnie sortować duże zbiory danych. Oba algorytmy mają wiele zastosowań w świecie rzeczywistym, od przeszukiwania baz danych i handlu finansowego po uczenie maszynowe i sekwencjonowanie DNA. W tym artykule przedstawiam szczegółowy przewodnik po obu algorytmach, w tym ich implementacje, przypadki użycia i zastosowania w świecie rzeczywistym. Niezależnie od tego, czy jesteś początkującym, czy doświadczonym programistą, te zaawansowane algorytmy mogą pomóc w rozwiązywaniu problemów w kodzie iw świecie rzeczywistym. Jeśli chcesz dowiedzieć się więcej o algorytmach, możesz przeczytać książkę„Grokking Algorithms: Ilustrowany przewodnik dla programistów i innych ciekawskich” Aditya Bhargava .

W następnym artykule omówię inny popularny algorytm: BFS (przeszukiwanie wszerz). Algorytm ten służy do eksploracji wszystkich wierzchołków grafu.