חיפוש בינארי מוסבר בפשטות¶
חיפוש בינארי הוא אחד האלגוריתמים שהכי משתלמים ללמוד, כי הוא פשוט, הוא שימושי, והוא כמעט תמיד מופיע בראיונות עבודה הראשונים בהייטק. אם עדיין לא כתבתם אותו בעצמכם, זה בדיוק הזמן.
המשחק "נחש את המספר" שכולנו שיחקנו¶
תזכרו את המשחק שבו מישהו חושב על מספר בין 1 ל-100, ואתם מנחשים עד שאתם פוגעים? השחקן הכי גרוע פשוט מתחיל לנחש 1, 2, 3, ברצף. השחקן הכי חכם שואל "50?" ומקבל תשובה "גבוה מדי" או "נמוך מדי", ואז שואל "25?" וממשיך לחצות את הטווח שנשאר בכל ניחוש.
זה בדיוק חיפוש בינארי. במקום לבדוק איבר אחרי איבר, אתם קופצים תמיד לאמצע הטווח שנשאר, ולפי התשובה זורקים חצי מהאפשרויות. זה ממש הכל.
התנאי החשוב שכולם שוכחים¶
יש כלל ברזל אחד: הרשימה חייבת להיות ממוינת מראש. חיפוש בינארי בכלל לא עובד על רשימה לא מסודרת, כי כל הרעיון מבוסס על היכולת לדעת שאם המספר האמצעי גדול מדי, אז כל מה שאחריו גם גדול מדי ואפשר לזרוק את כל הצד הזה בבת אחת. בלי סדר, אין שום דרך להסיק את זה.
זו הסיבה שאלגוריתמי מיון ואלגוריתמי חיפוש קשורים כל כך זה לזה - לפעמים משתלם למיין רשימה קודם, ואז לחפש בה הרבה פעמים בחיפוש בינארי מהיר, במקום לחפש כל פעם מחדש בשיטה האיטית.
איך זה נראה בקוד, ברמת הרעיון¶
תדמיינו רשימה ממוינת של מספרים ואתם מחפשים ערך מסוים:
- תבדקו את האיבר שבדיוק באמצע הטווח.
- אם הוא שווה למה שאתם מחפשים, סיימתם.
- אם הוא גדול מדי, תזרקו את כל החצי הימני והמשיכו לחפש רק בחצי השמאלי.
- אם הוא קטן מדי, תזרקו את החצי השמאלי והמשיכו רק בימני.
- תחזרו על זה עד שמוצאים את הערך, או שנשאר טווח ריק - במקרה כזה הערך פשוט לא קיים ברשימה.
מה שיפה בזה זה שכל צעד זורק חצי מהאפשרויות שנשארו. רשימה עם אלף איברים? תמצאו את הערך תוך כעשרה צעדים לכל היותר. רשימה עם מיליון איברים? עדיין רק כעשרים צעדים. זו הסיבה שחיפוש בינארי נחשב O(log n), כמו שהסברנו בפוסט על Big O - הזמן גדל לאט מאוד גם כשהנתונים גדלים בענק.
למה זה נחשב שם קלאסי לתרגול¶
חיפוש בינארי מלמד שני דברים חשובים בבת אחת. הראשון הוא איך לחשוב על בעיה במונחים של "לחצות ולזרוק חצי" - טכניקה שחוזרת בעוד המון בעיות אלגוריתמיות. השני הוא כמה קל לטעות בפרטים הקטנים - איפה בדיוק לזוז אחרי כל השוואה, מתי לעצור, איך למנוע לולאה אינסופית אם עשיתם טעות קטנה בגבולות. אלה בדיוק סוגי הבאגים שגורמים למתכנתים מנוסים להיזהר, ולכן זה נבדק כל כך הרבה בראיונות - זה בודק תשומת לב לפרטים, לא רק הבנה עקרונית.
איפה זה משמש מעבר לתרגילי לימוד¶
- פונקציות חיפוש מובנות בשפות תכנות, כמו
bisectבפייתון, בנויות על חיפוש בינארי. - מסדי נתונים משתמשים בגרסאות מתקדמות של הרעיון כדי לאתר שורות במהירות.
- מערכות בקרת גרסאות כמו git משתמשות ברעיון דומה כדי לאתר את הקומיט שבו נכנס באג, בפקודה שנקראת bisect.
איך לתרגל את זה כמו שצריך¶
תכתבו חיפוש בינארי בעצמכם על רשימה של מספרים, בלי להשתמש בפונקציה מובנית. ואז תבדקו את עצמכם על המקרים הקיצוניים - מה קורה כשמחפשים ערך שלא קיים, מה קורה עם רשימה ריקה, מה קורה עם רשימה של איבר אחד. שם בדיוק מתגלים הבאגים שהופכים את התרגיל הזה לכל כך שימושי ללמידה.
בקורס התכנות הבסיסי שלנו יש בדיוק את התרגילים האלה, שבונים אתכם צעד אחר צעד עד שחיפוש בינארי הופך לטבעי לגמרי.
תתחילו את קורס התכנות הבסיסי כאן
לסיכום¶
חיפוש בינארי זה בדיוק המשחק "נחש את המספר" שכולנו שיחקנו כילדים, רק שהוא דורש רשימה ממוינת ומדויקות בפרטים הקטנים. תלמדו לכתוב אותו טוב פעם אחת, ותשתמשו ברעיון מאחוריו שוב ושוב לאורך כל הקריירה שלכם.
תקועים בתרגיל? בואו לדיסקורד שלנו ותשאלו, יש שם אנשים שישמחו לעזור.