Bináris keresési (Binary Search) algoritmus be Java

A bináris keresési algoritmus egy hatékony Java programozási módszer, amely egy adott érték megtalálására szolgál egy rendezett tömbön belül. Ez a megközelítés folyamatosan két részre osztja a tömböt, és összehasonlítja a keresési értéket a középső elemmel.

Hogyan működik a bináris keresési algoritmus

A bináris keresési algoritmus a keresési érték és a tömb középső elemének összehasonlításával kezdődik. Ha a keresési érték megegyezik a középső elemmel, akkor az algoritmus az adott elem pozícióját adja vissza. Ha a keresési érték kisebb, mint a középső elem, akkor az algoritmus a tömb bal felében folytatja a keresést. Ha a keresési érték nagyobb, akkor az algoritmus a tömb jobb felében folytatja a keresést. Ez a folyamat addig ismétlődik, amíg meg nem találja a keresett értéket, vagy nincs több keresendő elem.

A bináris keresési algoritmus előnyei és hátrányai

Előnyök:

• Nagy hatékonyság: Ez az algoritmus minden lépésben kiküszöböli az elemek felét, optimalizálva a nagy tömbök keresését.
• Alacsony idejű összetettség: Ennek az algoritmusnak az időbonyolultsága O(log n), így nagy adatkészletek esetén is hatékony.

Hátrányok:

• Rendezett tömb követelmény: Az algoritmus csak rendezett tömbökkel működik.

Példa és magyarázat

Tekintsünk egy példát a bináris keresési algoritmus használatára egy adott egész szám megkeresésére egy rendezett egész szám tömbben a -ban 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");  
        }  
    }  
}  

Ebben a példában a bináris keresési algoritmust használjuk a 9-es szám megtalálásához egy rendezett egész tömbben. Az algoritmus végigfut a tömbön, és összehasonlítja a keresési értéket a középső értékkel. Ebben az esetben a 9-es szám a tömb 4. pozíciójában(0-alapú index) található.

Míg ez a példa bemutatja, hogy a bináris keresési algoritmus hogyan talál egy elemet egy rendezett egész szám tömbben, a programozásban más keresési forgatókönyvekre is alkalmazható Java.