Binární vyhledávací (Binary Search) algoritmus v Java

Binary Search Algorithm je efektivní metoda v Java programování, která se používá k nalezení konkrétní hodnoty v seřazeném poli. Tento přístup průběžně rozděluje pole na dvě části a porovnává hledanou hodnotu se středním prvkem.

Jak funguje binární vyhledávací algoritmus

Binární vyhledávací algoritmus začíná porovnáním hledané hodnoty se středním prvkem pole. Pokud je hledaná hodnota rovna prostřednímu prvku, algoritmus vrátí polohu tohoto prvku. Pokud je hledaná hodnota menší než prostřední prvek, algoritmus pokračuje v hledání v levé polovině pole. Pokud je hledaná hodnota větší, algoritmus pokračuje v hledání v pravé polovině pole. Tento proces se opakuje, dokud není nalezena hledaná hodnota nebo dokud nejsou k prohledávání žádné další prvky.

Výhody a nevýhody binárního vyhledávacího algoritmu

výhody:

• Vysoká účinnost: Tento algoritmus eliminuje polovinu prvků v každém kroku, čímž optimalizuje vyhledávání velkých polí.
• Nízká časová složitost: Časová složitost tohoto algoritmu je O(log n), díky čemuž je efektivní pro velké datové sady.

Nevýhody:

• Požadavek na seřazené pole: Algoritmus pracuje pouze s seřazenými poli.

Příklad a vysvětlení

Zvažte příklad použití binárního vyhledávacího algoritmu k nalezení konkrétního celého čísla v seřazeném celočíselném poli v 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");  
        }  
    }  
}  

V tomto příkladu používáme binární vyhledávací algoritmus k nalezení čísla 9 v seřazeném celočíselném poli. Algoritmus prochází polem a porovnává hledanou hodnotu se střední hodnotou. V tomto případě se číslo 9 nachází na pozici 4(index založený na 0) v poli.

I když tento příklad ukazuje, jak může binární vyhledávací algoritmus najít prvek v seřazeném celočíselném poli, lze jej použít i na jiné scénáře vyhledávání v Java programování.