Binary search - חיפוש בינארי

---

חיפוש בינארי הוא אלגוריתם יעיל למציאת אלמנט בתוך מערך ממוין. זה עובד על ידי חלוקה חוזרת של מרווח החיפוש לשניים ובדיקה אם האלמנט שמחפשים הוא קטן, גדול או שווה לאלמנט האמצעי של המרווח. אם האלמנט קטן מהאלמנט האמצעי, החיפוש ממשיך בחצי התחתון של המרווח. אם האלמנט גדול מהאלמנט האמצעי, החיפוש ממשיך בחצי העליון של המרווח. אם האלמנט שווה לאלמנט האמצעי, החיפוש מצליח והאינדקס של האלמנט מוחזר.

להלן דוגמה כיצד ליישם חיפוש בינארי ב- Python:

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1

פונקציה זו לוקחת רשימה ממוינת arr ואלמנט חיפוש x, ומחזירה את האינדקס של x ב-arr אם הוא קיים, או -1 אם הוא אינו קיים.

לחיפוש בינארי יש מורכבות זמן של O(log n), מה שהופך אותו למהיר הרבה יותר מחיפוש ליניארי של מערכים גדולים. עם זאת, ניתן להשתמש בו רק על מערכים ממוינים, וזה מחייב את המערך מראש.