נגדיר: מערך חד-ממדי nums המלא במספרים שלמים נקרא כמעט-ממוין (almost sorted) אם הוא ממוין בסדר עולה, אבל חלק מהאיברים של המערך התחלפו עם אחד מהשכנים שלהם.
כלומר, יתכן שזוגות של איברים סמוכים התחלפו במקומם. האיבר nums[i] יכול להיות בתא nums[i-1] או nums[i+1]
המערך הבא הוא מערך ממוין [3, 10, 20, 40, 50, 70, 80]
והמערך הבא הוא מערך כמעט-ממוין [10, 3, 40, 20, 50, 80, 70]
כיוון שהאיברים בתאים 0 ו-1 הוחלפו, האיברים בתאים 2 ו-3 התחלפו וכך גם האיברים בתאים 5 ו-6.
נתון מערך חד-ממדי nums המלא במספרים שלמים שהוא כמעט-ממוין, ומספר שלם target יש להחזיר את המיקום של הערך target במערך nums אם הערך target לא נמצא במערך nums יוחזר הערך -1.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
nums = [10, 3, 40, 20, 50, 80, 70], target = 40
2
הסבר: הערך 40 נמצא במערך באינדקס 2
nums = [10, 3, 40, 20, 50, 80, 70], target = 60
-1
הסבר: הערך 60 אינו נמצא במערך
nums = [10, 3, 40, 20, 50, 80, 70], target = 80
5
הסבר: הערך 80 נמצא במערך באינדקס 5
nums = [10, 3, 40, 20, 50, 80, 70], target = 10
0
הסבר: הערך 10 נמצא במערך באינדקס 0
nums = [5, 10, 30, 20, 40, 50, 60], target = 30
2
הסבר: הערך 30 נמצא במערך באינדקס 2
nums = [1, 3, 5, 4, 7, 6, 8, 10, 9], target = 7
4
הסבר: הערך 7 נמצא במערך באינדקס 4
nums = [10, 20, 25, 40, 35, 50, 60], target = 35
4
הסבר: הערך 35 נמצא במערך באינדקס 4, כאשר התחלף מהמקום המקורי שלו באינדקס 3
nums = [100, 90, 80, 75, 65, 70, 60, 50], target = 75
3
הסבר: הערך 75 נמצא במערך באינדקס 3. שים לב שהמערך יורד בסדר כמעט-ממוין, אך השיטה עדיין מחזירה את המיקום הנכון.
קלט:
nums = [10, 3, 40, 20, 50, 80, 70], target = 40
הפלט המבוקש:
2