חיפוש וחציה.

שלב 1 מתוך 5

חיפוש סדרתי

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

שלב 2 מתוך 5

חיפוש בינארי

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

שלב 3 מתוך 5

כמה חציות

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

מספר ההכפלות של 2 שמגיעות ל־$n$⁠ הוא הלוגריתם לפי בסיס שתיים, $\log_2 n$⁠. חיפוש בינארי ב־$n$⁠ שמות ממוינים צריך בערך $\log_2 n$⁠ בדיקות.

שלב 4 מתוך 5

רשימה כפולה

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

שלב 5 מתוך 5

מיליון

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