a הוא מערך המכיל מספרים שלמים ממוין בסדר עולה ממש (כלומר המספרים שונים זה מזה).
נגדיר מערך טווחים של a כמערך שנבנה באופן הבא: עבור כל רצף של מספרים עוקבים ב-a, יהיה במערך הטווחים אובייקט שמכיל שני שדות של מספרים שלמים. שדה אחד הוא המספר המרכזי ברצף (center) ושדה שני הוא "רדיוס" הרצף (radius), כלומר, מספר התאים מימין ומשמאל ששייכים לרצף. רצף יכול להיות באורך 1 או יותר, אבל הרצפים תמיד הם באורכים אי-זוגיים.
אם הרצף באורך 1 הוא מיוצג במערך המחושב על ידי אובייקט ששני השדות שלו שווים.
לדוגמה, עבור המערך a (סימנו את הרצפים השונים במערך, כדי להדגיש אותם).
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 3 | 4 | 5 | 12 | 19 | 20 | 21 | 100 | 101 | 102 | 103 | 104 |
מערך הטווחים rangeA יהיה:
| 0 | 1 | 2 | 3 |
| <4, 1> | <12, 0> | <20, 1> | <102, 2> |
(כל אובייקט מסומן כזוג סדור עם סוגריים משולשים).
לשם כך הגדרנו מחלקה בשם Range בה כל אובייקט מייצג תחום של מספרים לפי המתואר לעיל. להלן המחלקה Range:
בהינתן מערך טווחים rangeA ומספר num. אם המספר num נמצא במערך המקורי (a) שמיוצג על ידי מערך הטווחים rangeA, יש להחזיר את האינדקס במערך הטווחים בו נמצא ערכו של num. אם המספר לא נמצא יוחזר -1.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
מערך הטווחים מייצג בצורה נכונה את המערך המקורי הממוין.
אין חפיפות בין הטווחים.
rangeA = [[4, 1], [12, 0], [20, 1], [102, 2]], num = 5
0
הסבר: נמצא באובייקט בתא 0 במערך הטווחים.
rangeA = [[4, 1], [12, 0], [20, 1], [102, 2]], num = 101
3
הסבר: נמצא באובייקט בתא 3 במערך הטווחים.
rangeA = [[4, 1], [12, 0], [20, 1], [102, 2]], num = 15
-1
הסבר: 15 לא נמצא באף טווח.
rangeA = [[4, 1], [12, 0], [20, 1], [102, 2]], num = 105
-1
הסבר: 105 לא נמצא באף טווח.
קלט:
rangeA = [[4, 1], [12, 0], [20, 1], [102, 2]], num = 5
הפלט המבוקש:
0