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.

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.