Binary Search (wyszukiwanie binarne) w C#

Binary Search

Algorytm Binary Search (inaczej znany jako wyszukiwanie binarne) to efektywny algorytm służący do wyszukiwania elementu w posortowanym zbiorze danych.
Działa on przez podział zbioru na dwie połowy i porównywanie wartości środkowej z elementem, który jest poszukiwany.
Na podstawie wyniku porównania algorytm decyduje. Czy element znajduje się w lewej lub prawej połowie zbioru, eliminując jedną z połówek przy każdej iteracji.
Algorytm jest kontynuowany, aż do znalezienia szukanego elementu lub stwierdzenia, że nie istnieje w zbiorze.

Oto kroki algorytmu Binary Search:

1. Inicjalizacja: Rozpoczynamy od posortowanego zbioru danych i znamy element, który chcemy znaleźć.
2. Ustalenie zakresu: Określamy zakres, w którym będziemy wyszukiwać. Początkowo jest to cały zbiór, czyli od pierwszego do ostatniego elementu.
3. Porównanie: Obliczamy środkowy element w aktualnym zakresie i porównujemy go z elementem, który poszukujemy.
4. Decyzja: Jeśli środkowy element jest równy poszukiwanemu elementowi, algorytm kończy działanie, ponieważ znalazł szukany element.
5. Skrajne wartości: Jeśli poszukiwany element jest mniejszy od środkowego elementu. To skrajna prawa granica zakresu zostaje przesunięta do elementu środkowego minus jeden. W przeciwnym przypadku skrajna lewa granica zakresu jest przesuwana do elementu środkowego plus jeden.
6. Iteracja: Algorytm powtarza te kroki, zmniejszając zakres wyszukiwania w każdej iteracji. Aż znajdzie szukany element lub stwierdzi, że nie ma go w zbiorze.
7. Zakończenie: Algorytm kończy działanie, gdy znajdzie poszukiwany element lub gdy skrajne wartości granic zakresu się przetną. Oznacza to, że element nie istnieje w zbiorze.

Główną zaletą algorytmu Binary Search jest jego efektywność. Dzięki podziałowi zbioru na dwie połowy w każdej iteracji, wyszukiwanie jest znacznie szybsze niż w przypadku liniowego wyszukiwania. Jednakże warunkiem koniecznym jest, aby zbiór danych był posortowany, co może być jego ograniczeniem w niektórych przypadkach.

Złożoność czasowa algorytmu Binary Search wynosi O(log n). Oznacza to, że czas potrzebny do znalezienia elementu maleje logarytmicznie wraz ze wzrostem rozmiaru zbioru danych.

Krok po kroku na przykładzie

Prześledźmy wyszukiwanie liczby 10 w tablicy { 2, 4, 6, 8, 10, 12, 14, 16 } (indeksy 0–7):

Trzy iteracje wystarczyły, żeby przeszukać 8-elementową tablicę — dla 1000 elementów wystarczyłoby tylko 10 iteracji (log₂ 1000 ≈ 10), bo za każdym razem odrzucamy połowę pozostałego zakresu.

Implementacja

using System;

class BinarySearch
{
    // Funkcja binarySearch przyjmuje posortowany zbior danych (tablicę) oraz element, który chcemy znaleźć.
    // Zwraca indeks znalezionego elementu lub -1, jeśli element nie istnieje w zbiorze.
    static int binarySearch(int[] arr, int target)
    {
        int left = 0;            // Początkowy indeks lewej granicy zakresu.
        int right = arr.Length - 1; // Początkowy indeks prawej granicy zakresu.

        while (left <= right)
        {
            int middle = left + (right - left) / 2; // Oblicz środkowy indeks zakresu.

            // Jeśli środkowy element jest szukanym elementem, zwracamy jego indeks.
            if (arr[middle] == target)
                return middle;

            // Jeśli szukany element jest mniejszy od środkowego elementu,
            // zawężamy zakres do lewej połowy.
            if (arr[middle] > target)
                right = middle - 1;

            // W przeciwnym razie zawężamy zakres do prawej połowy.
            else
                left = middle + 1;
        }

        // Element nie został znaleziony w zbiorze.
        return -1;
    }

    public static void Main(string[] args)
    {
        int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16 };
        int target = 10;

        int result = binarySearch(arr, target);

        if (result != -1)
            Console.WriteLine($"Element {target} został znaleziony na indeksie {result}");
        else
            Console.WriteLine($"Element {target} nie istnieje w zbiorze.");

        // Oczekiwany wynik: "Element 10 został znaleziony na indeksie 4"
    }
}

Algorytm działa na posortowanej tablicy liczb całkowitych i zwraca indeks znalezionego elementu lub -1, jeśli element nie istnieje w zbiorze.

Wbudowana alternatywa — nie zawsze musisz pisać to sam

int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16 };
int index = Array.BinarySearch(arr, 10); // wbudowana implementacja, ten sam algorytm

var lista = new List { 2, 4, 6, 8, 10, 12, 14, 16 };
int indexLista = lista.BinarySearch(10); // odpowiednik dla List<T>

Array.BinarySearch i List<T>.BinarySearch robią dokładnie to, co własnoręczna implementacja powyżej — warto znać własną implementację, żeby rozumieć mechanikę i móc odpowiedzieć na pytanie rekrutacyjne, ale w kodzie produkcyjnym zwykle sięgniesz po wbudowaną wersję, chyba że potrzebujesz niestandardowego porównania (przeciążenie z IComparer<T>).

Powiązane: alternatywa bez sortowania to wyszukiwanie liniowe; dane najpierw uporządkujesz np. przez Merge Sort. Zobacz też klasyfikację algorytmów.