חיפוש בינארי

הקדמה:

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

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

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

חיפוש בינארי לא רק עוזר לשחק משחקים, אלא גם בפתרון בעיות בחיים. דמיינו, לדוגמא, מצב בו ישנה רשימה של \({4}\) פעילויות חברתיות אפשריות, נאמר: אוכל, סרט, ים ובריכה. ושאתם מעוניינים לתאם עם חבריכם את הפעילות למחר. כמה שאלות כן-לא נדרשות על מנת לדעת מהי הפעילות העדיפה עליהם? באופן דומה, דמיינו שאתם רוצים לברר מספר טלפון של אדם שזה אתה פגשתם. כמה שאלות כן-לא דרושות על מנת להשיג זאת?

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

הגדרות:

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

\(\displaystyle .1,2,3,\ldots,n\)

כל מספר ברשימה מתאים לאחת הדמויות האפשריות, או לאחת הפעילויות האפשריות, או לאחד ממספרי הטלפון האפשריים. נניח שלחברנו ידוע מספר \({X}\) מתוך רשימת המספרים, ואנו לא יודעים מהו \({X}\). כמו כן נניח כי אנו יכולים לשאול את חברנו כל שאלת כן-לא העולה על רוחנו. למשל, “האם \({X}\) הוא לפחות 12?״. השאלה שתנחה אותנו היא:

מהו המספר הקטן ביותר \({Q}\) של שאלות כן-לא הדרושות כדי לדעת מהו \({X}\)?

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

המשפט המתמטי הבא מתאר את התשובה לשאלה, ונוכיחו בהמשך.

משפט: לכל מספר \({n}\) טבעי, מתקיים \({.2^{Q-1} < n \leq 2^{Q}}\)

כדי להבין את המשפט טוב יותר, נתבונן בגרף 1 שמתאר את הקשר בין מספר השאלות \({Q}\) ומספר האפשרויות \({n}\) עבור ערכי \({n}\) בין \({1}\) ל \({200}\).

QnSort

גרף \({:1}\) קשר בין מספר שאלות מינימלי למספר האפשרויות

הגרף מראה למשל שאם ישנן 20 אפשרויות \({(n=20)}\) אז נזדקק ל \({5}\) שאלות, ואם \({n=200}\) אז נזדקק ל \({8}\) שאלות. כמו כן, ניתן לראות שהתלות בין \({Q}\) ל \({n}\) אינה לינארית, כלומר אינה מתוארת על ידי קו ישר. סוג הקשר בין \({Q}\) ל \({n}\) נקרא קשר לוגריתמי. המשפט גם מתאר כמה שאלות כן-לא דרושות על מנת לגלות מספר טלפון בן שבע ספרות: דרושות בסך הכל עשרים וארבע שאלות! מהן השאלות? זאת נראה בהמשך (באופן מופשט).

הוכחת המשפט:

להוכחה שני חלקים שונים. אי השיוויון השמאלי משמעותו מציאת רשימת שאלות קצרה שמבטיחה שלאחר שנשאל את כולה נדע את המידע החבוי \({X}\). אי השיוויון הימני משמעותו שאם רשימת השאלות קצרה מדי אז בסיומה עדיין תהיה חוסר וודאות לגבי הערך המדויק של \({X}\).

אי השיוויון הימני: מעט שאלות לא מספיקות

נתחיל בלהוכיח את הטענה הבאה: לכל \({L \geq 0}\) טבעי, ולכל רשימת שאלות כן-לא באורך \({L}\), ישנה קבוצה בגודל לפחות \({n/2^L}\) של מספרים בין \({1}\) ל \({n}\) שרשימת השאלות לא מבדילה בניהם (כלומר כך שהתשובות לכל \({L}\) השאלות הן זהות לכל המספרים בקבוצה).

הוכחת הטענה: עבור \({L=0}\), טענה זו כמובן נכונה כי לא נשאלה אף שאלה ו \({2^0=1}\). עבור \({L=1}\), קבוצת האפשרויות מתחלקת לשני חלקים בהתאם לתשובה לשאלה שנשאלה. אחד משני החלקים חייב להיות לכן בגודל לפחות חצי, כלומר בגודל לפחות \({n/2}\). נבחר חלק זה. עבור \({L=2}\), נתבונן בחלק שנבחר לאחר השאלה הראשונה וגודלו לפחות \({n/2}\). נשים לב שלאחת התשובות לשאלה השניה יש תשובה שלה מתאימים לפחות \({\frac{1}{2} \cdot n/2 = n/2^2}\) אפשרויות, וכן הלאה.

מסקנה מהטענה: אם \({2^L < n}\) אז בכל רשימה של \({L}\) שאלות ישנם לפחות שני מספרים שונים \({(n/2^L > 1)}\) שהשאלות לא מבדילות בניהם. אם כך, בכמות כזו של שאלות לא נצליח באופן וודאי לגלות את ערך \({X}\). לכן, \({2^Q \geq n}\).

אי השיוויון השמאלי: בחירת השאלות

עלינו למצוא סדרת שאלות מתאימה. הרעיון הוא להשתמש בחיפוש בינארי, המתבצע כך: ישנם \({n}\) מספרים. נגדיר \({M}\) להיות הטבעי הקטן ביותר כך ש \({n \leq 2^M}\). מינימליות \({M}\) גוררת ש \({2^{M-1} < n}\). נסביר כיצד לגלות את \({X}\) בעזרת \({M}\) שאלות כן-לא. בכך נסיים ההוכחה.

השאלה הראשונה שנשאל היא ״האם \({X<(1/2) \cdot 2^{M}}\)?״. אם התשובה היא כן, נמשיך ונשאל ״האם \({X<(1/4) \cdot 2^{M}}\)?״ ואחרת נשאל ״האם \({X<(3/4) \cdot 2^M}\)?״. וכן הלאה. ניתן לראות שלאחר השאלה הראשונה כמות האפשרויות ל \({X}\) היא לכל היותר \({\frac{1}{2} \cdot 2^M = 2^{M-1}}\). לאחר השאלה השניה הכמות קטנה ל \({2^{M-2}}\). באופן כללי, לאחר \({L}\) שאלות כמות האפשרויות תהיה \({2^{M-L}}\). לאחר \({M}\) שאלות כמות האפשרויות היא \({2^{M-M} = 1}\), כלומר נדע את \({X}\) בוודאות.

ייצוג בינארי:

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

ייצוג עשרוני של מספר הוא דבר מוכר לכולם. לכל כפולה של עשר יש ספרה משלה: ספרת אחדות \({10^0 = 1}\), ספרת עשרות \({10^1 = 10}\), ספרת מאות \({10^2 = 100}\)… והסימון \({106}\) מייצג את המספר \({1 \times 100 + 0 \times 10 + 6 \times 1}\).

באופן דומה, ניתן לייצג מספר בינארית, בבסיס שתיים במקום בבסיס עשר. במקום עשר ספרות, ישנן רק שתיים: \({0,1}\). בייצוג זה ישנה ספרה שמתאימה ל \({2^0 = 1}\), ספרה שמתאימה ל \({2^1 = 2}\), ספרה שמתאימה ל \({2^2 = 4}\)… והסימון \({101}\) מייצג למשל את \({1 \times 4 + 0 \times 2 + 1 \times 1}\), כלומר את המספר חמש.

מה הקשר לשאלות כן-לא? ובכן ניתן לפרש את הספרה \({1}\) כ״לא״ ואת הספרה \({0}\) כ״כן״. עם פרשנות זו, ייצוג בינארי מתאים בדיוק לתשובות המתקבלות בחיפוש הבינארי שדיברנו עליו. למשל אם \({n=8}\) ו \({X = 5}\), נשאל ״האם \({X < 4}\)?״ והתשובה תהיה ״לא״. תשובה זו מתאימה ל \({1}\) השמאלי בייצוג הבינארי של חמש. נמשיך ונשאל ״האם \({X < 6}\)?״ והתשובה ״כן״ מתאימה ל \({0}\). לסיום, התשובה ל ״האם \({X<5}\)?״ היא ״לא״ ומתאימה ל \({1}\) הימני.

באופן מעט יותר כללי, תיארנו קשר בין הייצוג הבינארי של מספר לבין תשובות לשאלות כן-לא לגביו. אם למספר יש \({21}\) ספרות בייצוג הבינארי, אז ניתן למצוא אותו בפשטות על ידי שאילת \({21}\) שאלות: ״האם הספרה הראשונה היא \({0}\)?״, ״האם הספרה השניה היא \({0}\)?״, וכן הלאה. יש קשר ישיר בין הייצוג הבינארי של מספר ובין התשובות לרשימת השאלות הזו. מכך נסיק שבאמצעות \({21}\) שאלות אפשר לתאר \({2^{21} = 2,097,152}\) דברים! לשם השוואה, מספר המילים במילון בשפה העברית הוא קטן בהרבה, ומוערך להיות פחות מ \({100,000}\).

נסיים במחשבה על כפות ידינו. בדרך כלל משתמשים באצבעות כדי לייצג מספרים בין אחד לעשר. עכשיו כשלמדנו מעט, אנחנו מבינים שעם חמש האצבעות של כף יד אחת ניתן לייצג בפשטות \({2^5 = 32}\) מספרים. תנסו. כמה אפשר עם כל עשר האצבעות?