חיפוש בינארי (Binary Search)

הרעיון

תנאי מקדים: המערך חייב להיות ממוין (בסדר עולה).

1. הגדר low = 0 ו-high = length - 1.
2. חשב mid = (low + high) / 2.
3. אם arr[mid] == key – מצאנו! מחזירים mid.
4. אם arr[mid] < key – הערך בחצי הימני: low = mid + 1.
5. אם arr[mid] > key – הערך בחצי השמאלי: high = mid - 1.
6. חוזרים ל-2 כל עוד low ≤ high.

דוגמה מצוירת

חיפוש הערך 23 במערך {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}:

מצאנו את 23 באינדקס 5 תוך 3 צעדים בלבד (במקום עד 10 בחיפוש לינארי).

קוד – חיפוש בינארי איטרטיבי

public static int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1; // לא נמצא
}

קוד – חיפוש בינארי רקורסיבי

public static int binarySearchRec(int[] arr, int key, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;

    if (arr[mid] == key)
        return mid;
    else if (arr[mid] < key)
        return binarySearchRec(arr, key, mid + 1, high);
    else
        return binarySearchRec(arr, key, low, mid - 1);
}

קריאה: binarySearchRec(arr, key, 0, arr.length - 1)

סיבוכיות

דוגמאות מספריות

השוואה – לינארי מול בינארי