שיעור 8: חיפוש בינארי

נשחק ניחוש: חשבתי על מספר בין 1 ל-100, ובכל ניסיון אני אומר/ת 'גבוה' או 'נמוך'. הדרך החכמה: לנחש כל פעם את האמצע ולפסול חצי מהאפשרויות. זה בדיוק 'חיפוש בינארי' — אלגוריתם שמוצא ערך ברשימה ממוינת, וחוצה את המועמדים בכל צעד. התוצאה: O(log n), מהיר להפליא — גם על מיליארד פריטים מספיקות כ-30 בדיקות.

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

חיפוש בינארי: אלגוריתם חיפוש על מערך ממוין שבכל צעד בודק את האמצע וזורק את החצי שלא יכול להכיל את היעד — O(log n).
זמן לוגריתמי: O(log n): מספר הצעדים גדל לאט מאוד — כל הכפלה של n מוסיפה צעד אחד בלבד, כי מרחב החיפוש נחצה בכל פעם.
מרחב חיפוש: טווח האינדקסים [low, high] שעדיין עשוי להכיל את היעד; חיפוש בינארי מקטין אותו פי 2 בכל איטרציה.