אתגר תכנותי: מציאת מינימום במערך מסובב

האתגר

נתון מערך מספרים `nums` המסודרים בסדר עולה, אך הם עשויים להיות "מסובבים" סביב נקודת ציר כלשהי. "מערך מסובב" הוא מערך בו נקודת ציר מחלקת את המערך, והמספרים מסתדרים סביב הציר כמו ציר של דלת.

לדוגמה:

nums = [0, 1, 2, 3, 4]

אשר מסובב סביב אינדקס 2 ייראה כך:

nums_with_pivot = [3, 4, 0, 1, 2]

• המספרים שהיו מימין ל-2 במערך המקורי עברו לתחילת המערך.

האתגר הוא לכתוב פונקציה המקבלת מערך מסובב, ומחזירה את הפריט בעל הערך הנמוך ביותר. בנוסף, סיבוכיות הזמן של הקוד צריך להיות O(LOG N).

דוגמה 1:

input = [5, 6, 7, -1, 2]
output = -1

דוגמה 2:

output = [2,3,8,6]
output = 2

פתרון

הדרישה היא לחיפוש עם סיבוכיות זמן O(LOG N) מה שרומז על שימוש באלגוריתם חיפוש בינארי.

ננסה להבין איך לפתור על ידי זה שנעבוד על המערך הבא:

[5,6,7,-1,2,3]

חיפוש בינארי חוצה את המערך לשניים, ובכל שלב מצמצם את מרחב החיפוש בחצי.

בשלב הראשון, הפריט האמצעי הוא 7. עכשיו אנחנו צריכים לשאול האם כדאי לנו לחפש בחצי מימינו או משמאלו. משמאלו נמצאים מספרים שכולם קטנים ממנו וזה צפוי במערך מסודר בסדר עולה אבל מימינו גם כן נמצאים מספרים הקטנים ממנו, וזה אומר שציר הסיבוב נמצא מימינו, וזה גם המקום בו נמצא הפריט המינימלי, בהתאם נצמצם את מרחב החיפוש לחצי הימני בלבד:

-1,2,3]

בשלב השני, הפריט האמצעי הוא 2. הפריט שמימינו גדול יותר (3), והפריט שמשמאל קטן יותר (1-). החצי הימני לא מעניין אותנו כי מה שנמצא בו הוא ערך גבוה יותר. מה שמעניין הוא החצי השמאלי בו נמצא האיבר הנמוך יותר. ומכיוון ש 1- הוא האיבר האחרון שנשאר לנו, נסיק שזה האיבר המינימלי.

הקוד האלגנטי הבא מיישם את הרעיון:

def find_min(nums):
   l, r = 0, len(nums)-1
   while l < r:
       m = (l+r)//2
       if nums[m] > nums[r]:
           l = m+1 # search in the right half
       else:
           r = m # search in the left half
   return nums[l]

נבחן את הקוד באמצעות מספר דוגמאות:

test_cases = [
   [[5,6,7,-1,2,3], -1],
   [[5,6,-2,-1,2], -2],
   [[7,-1,2,5,6], -1],
   [[1,3,6,8], 1],
   [[1,2,3,4,-2,-1,0], -2]
]


print(f"{'Result'.ljust(10)}{'Expected'.ljust(10)}{'Conclusion'}")
print(f"{'-'*10}{'-'*10}{'-'*10}")
# Loop through test cases and print results in table format
for nums, expected in test_cases:
   res = find_min(nums)
   conclusion = "😄" if res == expected else "😭"
   sign = "==" if res == expected else "!="
   print(f"{str(res).ljust(10)}{str(expected).ljust(10)}{conclusion}")


print("Finito Programa")

נסביר:

1. הקוד עורך חיפוש בינארי לצורך מציאת ערך המינימום במערך תחת המגבלה של סיבוכיות זמן O(LOG N). כרגיל בחיפוש בינארי נשתמש בשני מצביעים, שמאלי וימני (l ו-r).
2. הלולאה ממשיכה לרוץ כל עוד l < r
3. בכל פעם שהלולאה רצה מחושב האינדקס האמצעי באמצעות (l + r) // 2. מה שמחלק את המערך לשניים בכל איטרציה.
4. אם הערך עליו מצביע האינדקס האמצעי גדול יותר מזה עליו מצביע האינדקס הימני arr[m] > arr[r] זה אומר שציר הסיבוב נמצא בצד ימין, כשאנחנו יודעים שבציר הסיבוב נמצא פריט המערך בעל הערך הנמוך ביותר. בהתאם, נעדכן את האינדקס השמאלי ל l = m + 1 כדי שהחיפוש ימשיך בחצי הימני.
   האפשרות השנייה היא שציר הסיבוב נמצא בחצי השמאלי כולל האינדקס האמצעי, ואם זה המצב נמקד את החיפוש בחצי השמאלי על ידי הזזת האינדקס הימני לאמצע r = m
5. התנאי לסיום הוא כאשר האינדקס הימני והשמאלי שווים, מה שאומר שהחיפוש מתמקד בפריט אחד, שהוא בהכרח פריט המערך בעל הערך המינימלי.

לסיכום

מציאת ערך המינימום במערך מסובב מנצל את היתרונות של חיפוש בינארי כדי להגיע למינימום במערך מסובב תוך צמצום מרחב החיפוש בחצי בכל איטרציה מה שמוביל לקוד מאורגן ויעיל ולזמן ביצוע קצר.

מדריכים נוספים שעשויים לעניין אותך

אתגר תכנותי: חיפוש במערך מסובב

טכניקת חלון ההזזה sliding window לפתרון בעיות ברצפים

תכנות דינמי מלמטה למעלה ובחזרה - מדריך לתכנות דינאמי שמתחיל מהבסיס

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים