או שאני מפספס פה משהו,
או שממש הצלחתם לבלבל אותי. איפה כתוב שהמספרים במערך עוקבים?! זה לא כתוב בשום מקום. זה יכול להיות מערך של 5 מספרים - 1, 5, 87, 123, 789. זה מערך ממויין של מספרים שלמים, כאשר כל מספר אינו מופיע יותר מפעם אחת במערך. עכשיו, איך נגלה האם המספר 7 קיים במערך? זו שאלה לא קלה. השאלה השניה היא דווקא יותר פשוטה. בודקים באמת כמו שיאיר הציע, את ההפרש בין האיבר הראשון לאיבר האחרון. נניח שגודל המערך הוא N, אז יש שתי אפשרויות: ההפרש הוא N - ואז אין "מקום פנוי" במערך; או ההפרש גדול מ-N - ואז נניח שהוא N+1, בלי הגבלת הכלליות, ועכשיו עלינו למצוא את המקום הפנוי בתוך המערך. האלגוריתם הוא: (מערך "מלא" - ההפרש בין האחרון לבין הראשון + 1 שווה לגודל המערך) חלק את המערך לשני חלקים. בדוק האם המספר שאמור להיות המספר הנוכחי אכן במיקום הנוכחי (ראה הערה בהמשך) אם לא - החזר את המספר הנוכחי אם המערך הימני אינו "מלא", חלק אותו לשניים והמשך בתהליך. אחרת חלק את המערך השמאלי לשני חלקים והמשך בתהליך דוגמה: נניח שלפנינו המערך 1,2,4,5,6,7,8,9,10,11 - בן 10 איברים. המספר הפנוי הוא 3. נחלק את המערך לשני חלקים: (1,2,4,5,6) ו - (7,8,9,10,11). המערך הימני - 11..7 - מלא. המערך השמאלי לא מלא - נחלק אותו לשני חלקים, (1,2) ו - (4,5,6). אבל עכשיו חסר לנו בעצם ה - 3, וזיהינו אותו, כי במקום ה - 4 היה צריך להיות 3. נחזור לשאלה הראשונה. הימור שלי - כדי שזה יעבוד ב - (O(1, צריך לייצג את כל משתני המערך בבת אחת ביחד כך שפעולה חשבונית אחת תוכל לזהות אם האיבר קיים במערך... אבל פה נתקעתי
