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