"אריה במדבר" - מי מכיר?

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

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

אבל עד עכשיו לא נתקלתי במישהו שמכיר את השיטה הבסיסית הזו, וגם לא את השם "אריה במדבר" (אפילו לא גוגל). האם מישהו כאן מכיר?
 

דיברגנט חדש

Well-known member
לפני עשרות שנים, למדתי אלגוריתם חיפוש פשוט, שהוצג לי בשם "אריה במדבר". וזה הולך ככה: יש מדבר (שטח) גדול, ואיפשהו נמצא אריה. רוצים לדעת איפה.
מחלקים את השטח לשניים. בודקים באיזה חצי האריה נמצא. את החצי שהוא נמצא בו, מחלקים לשניים. וכן הלאה, עד שנשארים עם פיסת שטח כלכך קטנה, שהוא נאלץ לעמוד על רגל אחת. דוחפים אותו, והוא נופל.

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

אבל עד עכשיו לא נתקלתי במישהו שמכיר את השיטה הבסיסית הזו, וגם לא את השם "אריה במדבר" (אפילו לא גוגל). האם מישהו כאן מכיר?
ברור שמכיר והוא מאוד מוכר לכל מי שלמד באוניברסיטה מדעים מדוייקים ו/או הנדסה.
ע"י החיפוש הזה, מגיעים לסיבוכיות של logn.
 

AnarchistPhilosopher

Well-known member
ברור שמכיר והוא מאוד מוכר לכל מי שלמד באוניברסיטה מדעים מדוייקים ו/או הנדסה.
ע"י החיפוש הזה, מגיעים לסיבוכיות של logn.
למעט אם למדת מתמטיקה/פיזיקה כמוני.

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