מערך נקרא "ממוין מסובב" (Rotated Sorted Array) אם הוא מתקבל ממערך ממוין (עולה ממש) שעבר הזזה ציקלית (סיבובים) ימינה מספר פעמים. כלומר, לקחו מערך ממוין, חתכו את הסוף שלו והדביקו אותו להתחלה. לדוגמה, המערך הבא הוא ממוין מסובב: [15,20,25,1,5,8,10] (המערך המקורי היה: [1,5,8,10,15,20,25] ועבר הזזה).
שימו לב: גם מערך ממוין רגיל נחשב למערך מסובב (עם הזזה של 0).
הניחו כי כל איברי המערך שונים זה מזה.
א. (10 נק') כתבו אלגוריתם המוצא את האינדקס של האיבר המינימלי במערך (בדוגמה לעיל: האינדקס של 1). זמן הריצה הנדרש הוא לוגריתמי: O(logn). הסבירו בקצרה את נכונות האלגוריתם.
ב. (8 נק') כתבו אלגוריתם המקבל מערך ממוין מסובב ומספר כלשהו: x. האלגוריתם יחזיר את האינדקס של x במערך (או יחזיר "לא קיים"). זמן הריצה הנדרש הוא לוגריתמי: O(logn). הסבירו בקצרה את נכונות האלגוריתם.
ג. (7 נק') נניח כעת שאיברי המערך אינם בהכרח שונים (ייתכנו כפילויות), והמערך עדיין ממוין-מסובב. הראו שקיים קלט שעבורו האלגוריתם שכתבתם למציאת האיבר המינימלי יחזיר תשובה שגויה.