חשיבה אלגוריתמית
נוער

חיפוש בינארי לנוער: איך מוצאים מספר בלי לבדוק את כל הרשימה

במשחק ניחוש מספרים לא חייבים להתחיל מ-1 ולהמשיך אחד אחד. אם הרשימה מסודרת, אפשר לבדוק את האמצע, להשליך חצי מהאפשרויות ולמצוא תשובה בכמה צעדים.

עודכן: 20.10.2026
7 דקות קריאה
אלגוריתמים / Python

מה מחפשים, ואיך?

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

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

מוצאים את 21 בשלושה צעדים

  1. מסדרים את הרשימה

    חיפוש בינארי עובד כשהערכים ממוינים. בדוגמה שלנו: 2, 5, 8, 12, 16, 21, 30.

  2. בודקים את האמצע

    מחפשים את 21. הערך באמצע הוא 12. מכיוון ש-21 גדול מ-12, אין טעם להמשיך לחפש בחצי השמאלי.

  3. ממשיכים בחצי המתאים

    נשארים עם 16, 21, 30. הערך באמצע הוא 21, ולכן מצאנו את המספר.

איך כותבים את זה בפייתון?

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

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left <= right:
        middle = (left + right) // 2

        if numbers[middle] == target:
            return middle
        if numbers[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

numbers = [2, 5, 8, 12, 16, 21, 30]
print(binary_search(numbers, 21))  # 5

הפונקציה מחזירה מיקום ברשימה, לא את המספר עצמו. בפייתון סופרים מיקומים מאפס, ולכן 21 נמצא במיקום 5. הערך ‎-1 מסמן שלא נמצאה התאמה.

מה קורה כשהמספר חסר?

נסו לחפש 19 באותה רשימה. אחרי בדיקת האמצע עוברים לחצי הימני; שם בודקים 21 ואז נשארים עם 16. גם 16 אינו מתאים, ולא נשאר טווח לבדיקה. החיפוש נעצר ומחזיר ‎-1, בלי להיכנס ללולאה אינסופית.

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

טעויות שכדאי לתפוס מוקדם

מחפשים ברשימה לא ממוינת

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

מעדכנים את הגבול לא נכון

אחרי שבדקנו את האמצע, מוציאים אותו מהטווח הבא: עוברים ל-middle + 1 או ל-middle - 1.

שוכחים מקרה שלא נמצא

אם הגבול השמאלי עבר את הימני, נגמרו האפשרויות. הפונקציה צריכה להחזיר תוצאה ברורה.

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

תרגיל קטן להמשך

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