Algorytm wyszukiwania binarnego (Binary Search) w Java

Algorytm wyszukiwania binarnego to wydajna metoda Java programowania, używana do znajdowania określonej wartości w posortowanej tablicy. To podejście w sposób ciągły dzieli tablicę na dwie części i porównuje szukaną wartość ze środkowym elementem.

Jak działa algorytm wyszukiwania binarnego

Algorytm wyszukiwania binarnego rozpoczyna się od porównania szukanej wartości ze środkowym elementem tablicy. Jeżeli szukana wartość jest równa środkowi elementu, algorytm zwraca położenie tego elementu. Jeśli szukana wartość jest mniejsza niż środkowy element, algorytm kontynuuje wyszukiwanie w lewej połowie tablicy. Jeżeli wartość wyszukiwania jest większa, algorytm kontynuuje wyszukiwanie w prawej połowie tablicy. Proces ten powtarza się do momentu znalezienia szukanej wartości lub braku dalszych elementów do przeszukania.

Zalety i wady algorytmu wyszukiwania binarnego

Zalety:

• Wysoka wydajność: Algorytm ten eliminuje połowę elementów w każdym kroku, optymalizując wyszukiwanie dużych tablic.
• Niska złożoność czasowa: Złożoność czasowa tego algorytmu wynosi O(log n), co czyni go skutecznym w przypadku dużych zbiorów danych.

Niedogodności:

• Wymagania dotyczące posortowanej tablicy: Algorytm działa tylko z posortowanymi tablicami.

Przykład i wyjaśnienie

Rozważmy przykład użycia algorytmu wyszukiwania binarnego do znalezienia określonej liczby całkowitej w posortowanej tablicy liczb całkowitych w programie Java.

public class BinarySearchExample {  
    public static int binarySearch(int[] array, int target) {  
        int left = 0;  
        int right = array.length- 1;  
  
        while(left <= right) {  
            int mid = left +(right- left) / 2;  
  
            if(array[mid] == target) {  
                return mid; // Return position if found  
            } else if(array[mid] < target) {  
                left = mid + 1;  
            } else {  
                right = mid- 1;  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15 };  
        int target = 9;  
  
        int position = binarySearch(numbers, target);  
  
        if(position != -1) {  
            System.out.println("Element " + target + " found at position " + position);  
        } else {  
            System.out.println("Element " + target + " not found in the array");  
        }  
    }  
}  

W tym przykładzie użyjemy algorytmu wyszukiwania binarnego, aby znaleźć liczbę 9 w posortowanej tablicy liczb całkowitych. Algorytm iteruje po tablicy i porównuje szukaną wartość z wartością środkową. W tym przypadku liczba 9 znajduje się na pozycji 4(indeks oparty na 0) w tablicy.

Chociaż ten przykład pokazuje, jak algorytm wyszukiwania binarnego może znaleźć element w posortowanej tablicy liczb całkowitych, można go również zastosować do innych scenariuszy wyszukiwania w Java programowaniu.