חיפוש בינארי (נקרא גם "אריה במדבר") הוא אלגוריתם למציאת מקום של איבר במערך ממוּיין. ממוּיין פירושו שסדר האיברים מסודר מהקטן לגדול. האלגוריתם עובד על ידי בחינת החצי המתאים במערך בכל שלב, ולכן יש רק שתי אפשרויות בכל צעד, מצד שמאל או מצד ימין.
המטרה היא למצוא את מיקום איבר מסוים במערך בגודל n. בהשוואה לחיפוש סדרתי שמצריך O(n) פעולות, חיפוש בינארי מוצא את האיבר בזמן של O(log(n)). O(log(n)) משמעו שהמספר של שלבי החיפוש גדל לאט יחסית לגודל המערך.
בודקים את האיבר האמצעי של המערך. אם הוא האיבר המבוקש, מפסיקים. אם לא, משווים אותו לערך המבוקש. אם הערך המבוקש קטן מהאמצעי, ממשיכים בחצי השמאלי. אם הוא גדול, ממשיכים בחצי הימני. חוזרים על הפעולה על תת-המערך הנבחר עד שמוצאים את הערך או מגלים שהוא אינו במערך.
המערך מניח מיון עולה. מתחילים עם גבולות חיפוש (שמאל וימין). בכל איטרציה מחשבים אינדקס אמצעי, משווים לערך המבוקש, ומשנים את אחד מהגבולות לפי התוצאה. בתום התהליך נקבל את מיקום האיבר או שנקבל שאין אותו.
הרעיון בפסאודו-קוד הוא לקרוא לפונקציה עם גבולות שמאל וימין, לחשב middle, להשוות ולקרוא לפונקציה מחדש על חצי המתאים או להחזיר את middle כשיש התאמה.
בכל איטרציה המערך מצטמצם בחצי. לאחר k איטרציות גודל תת‑המערך הוא n/2^k. התהליך מסתיים כשנותר איבר אחד, ולכן k שווה ללוגריתם של n. מזה נובע שהסיבוכיות היא O(log(n)). זאת אומרת מספר הצעדים קטן משמעותית ממספר האיברים.
נבחן את המערך: 1,1,2,3,5,8,13,21,34,55 (סדר עולה). חיפשנו את המספר 2. אחרי חישובי אמצע ובחירת תת-המערך, האלגוריתם מצא את 2 והחזיר את המיקום 3.
השם "חיפוש בינארי" נובע מהבחירה בחצי אחד בכל שלב. הכינוי "אריה במדבר" נובע מבדיחה על מתמטיקאי שחולק את המדבר לשני חלקים עד שהוא מוצא את האריה.
חיפוש בינארי (גם "אריה במדבר") מוצא מקום של מספר במערך סדור. סדור פירושו שהמספרים מסודרים מהקטן לגדול.
המטרה היא לדעת היכן נמצא מספר בתוך רשימה ממוּיינת. השיטה חוסכת הרבה בדיקות.
בודקים את האיבר באמצע הרשימה. אם זה המספר, מסיימים. אם המספר קטן יותר, מחפשים בחצי השמאלי. אם גדול יותר, מחפשים בחצי הימני. חוזרים עד שמוצאים או נגמרים האיברים.
תתחיל מ"שמאל" ו"ימין". כל פעם קח את האמצע וראה אם זה המספר המבוקש. אחרי כל בדיקה מקטינים את תחום החיפוש לחצי.
בכל שלב אנחנו מקטינים את הרשימה בחצי. לכן מספר השלבים לא גדל מהר כשהרשימה גדולה.
הרשימה: 1,1,2,3,5,8,13,21,34,55. חיפשנו את 2. אחרי כמה בדיקות מצאנו אותו במקום מספר 3.
השם "אריה במדבר" זה בדיחה: מחלקים את המדבר לשניים עד שמוצאים את האריה.
תגובות גולשים