Wikiszótár

bináris keresés

Magyar

Kiejtés

  • IPA: [ ˈbinaːriʃkɛrɛʃeːʃ]

Főnév

bináris keresés

  1. (matematika, informatika, algoritmusok) A bináris keresés egy hatékony keresési algoritmus, amely rendezetten tárolt elemek között működik. Az algoritmus ismételten megfelezi a keresési tartományt, amíg a keresett értéket meg nem találja, vagy amíg a keresési tartomány üres nem lesz.


Elmélet

Algoritmus működése:

  1. Kezdjük a teljes lista (tömb) első és utolsó indexével.
  2. Határozzuk meg a középső elemet:  
  3. Hasonlítsuk össze a középső elemet a keresett értékkel:
    • Ha a középső elem megegyezik, a keresett elemet megtaláltuk.
    • Ha a középső elem kisebb, folytassuk a keresést a középső elem jobb oldali részén.
    • Ha a középső elem nagyobb, folytassuk a keresést a bal oldali részen.
  4. Ismételjük, amíg a keresési tartomány üres nem lesz.


Tulajdonságok

  • Időkomplexitás: (O(n)), mivel minden lépésben megfelezzük a keresési tartományt.
  • Térkomplexitás: (O(1)) iteratív változatban, (O(n)) rekurzív változatban a rekurzív hívások miatt.
  • Csak rendezett tömb esetén alkalmazható.


Pszeudokód

Iteratív változat

BinarySearch(A, x):
    bal = 0
    jobb = A hossza - 1

    amíg bal ≤ jobb:
        közép = (bal + jobb) // 2
        ha A[közép] == x:
            visszatér közép
        ha A[közép] < x:
            bal = közép + 1
        különben:
            jobb = közép - 1

    visszatér -1  // Nem található

Rekurzív változat

BinarySearchRec(A, x, bal, jobb):
    ha bal > jobb:
        visszatér -1  // Nem található
    közép = (bal + jobb) // 2
    ha A[közép] == x:
        visszatér közép
    ha A[közép] < x:
        visszatér BinarySearchRec(A, x, közép + 1, jobb)
    különben:
        visszatér BinarySearchRec(A, x, bal, közép - 1)

Python implementáció

Iteratív változat

def binary_search(arr, x):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid  # Elemek indexe
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # Elem nem található

# Példa
data = [2, 3, 4, 10, 40]
x = 10
result = binary_search(data, x)
if result != -1:
    print(f"Elem megtalálva a {result}. indexen")
else:
    print("Elem nem található")

Rekurzív változat

def binary_search_recursive(arr, x, left, right):
    if left > right:
        return -1  # Elem nem található
    mid = (left + right) // 2
    if arr[mid] == x:
        return mid
    elif arr[mid] < x:
        return binary_search_recursive(arr, x, mid + 1, right)
    else:
        return binary_search_recursive(arr, x, left, mid - 1)

# Példa
data = [2, 3, 4, 10, 40]
x = 10
result = binary_search_recursive(data, x, 0, len(data) - 1)
if result != -1:
    print(f"Elem megtalálva a {result}. indexen")
else:
    print("Elem nem található")

C++ implementáció

Iteratív változat

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(const vector<int>& arr, int x) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == x)
            return mid; // Elemek indexe
        else if (arr[mid] < x)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1; // Elem nem található
}

int main() {
    vector<int> data = {2, 3, 4, 10, 40};
    int x = 10;
    int result = binarySearch(data, x);

    if (result != -1)
        cout << "Elem megtalálva a " << result << ". indexen" << endl;
    else
        cout << "Elem nem található" << endl;

    return 0;
}

Rekurzív változat

#include <iostream>
#include <vector>

using namespace std;

int binarySearchRecursive(const vector<int>& arr, int x, int left, int right) {
    if (left > right)
        return -1; // Elem nem található

    int mid = left + (right - left) / 2;

    if (arr[mid] == x)
        return mid; // Elemek indexe
    else if (arr[mid] < x)
        return binarySearchRecursive(arr, x, mid + 1, right);
    else
        return binarySearchRecursive(arr, x, left, mid - 1);
}

int main() {
    vector<int> data = {2, 3, 4, 10, 40};
    int x = 10;
    int result = binarySearchRecursive(data, x, 0, data.size() - 1);

    if (result != -1)
        cout << "Elem megtalálva a " << result << ". indexen" << endl;
    else
        cout << "Elem nem található" << endl;

    return 0;
}

Összegzés

A bináris keresés egy gyors algoritmus, amely hatékonyan talál meg elemeket rendezett tömbökben. Kis térigényű és (O(n)) időkomplexitású, ezért nagy adathalmazokon különösen hasznos. Az iteratív és rekurzív változatok egyaránt könnyen implementálhatók.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=bináris_keresés&oldid=3479444”