Please ensure Javascript is enabled for purposes of website accessibility knowledgebase.co.il - מונחים - קטגוריה - מחשבים כללי - מה זה Binary search
אתם צופים ב: מה זה Binary search

מונחים מומלצים

מה זה Binary search

 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), מה שהופך אותו למהיר הרבה יותר מחיפוש ליניארי של מערכים גדולים. עם זאת, ניתן להשתמש בו רק על מערכים ממוינים, וזה מחייב את המערך מראש.

עליכם להתחבר על מנת להגיב בעמוד זה.