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

האתגר

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

לדוגמה:

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

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

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

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

דוגמה 1:

nums = [3, 4, 5, 1, 2]
target = 4
output = 1

דוגמה 2:

nums = [5, 8, 9, 0, 1, 3]
target = 2
output = -1

הצעה לפתרון

כיוון שהדרישה היא שהאלגוריתם ירוץ בסיבוכיות זמן של O(log N), אנו יכולים לחשוב על פתרון מבוסס חיפוש בינארי (binary search), אך ישנו "טוויסט" במקרה שלנו, מאחר שהמערך אינו מסודר באופן רגיל אלא מסובב. אז נצטרך להתמודד עם האתגר בדרך מעט שונה.

חיפוש בינארי בסיסי

חיפוש בינארי עובד כאשר המערך "מסודר". בגרסה הקלאסית, אנו חוצים את המערך לשניים, בודקים את הערך שבאמצע (`mid`), ומשווים אותו למספר המטרה. אם המטרה גדולה מערך האמצע, אנו מחפשים בחצי הימני של המערך, ואם היא קטנה - בחצי השמאלי. כך אנו מצמצמים את מספר האלמנטים בחיפוש בחצי בכל צעד.

קוד חיפוש בינארי איטרטיבי נראה כך:

def bin_search(nums, target):
    l = 0 # left pointer
    r = len(nums)-1 # right pointer
    while l <= r:
        m = (l+r)//2  # mid index
        if target == nums[m]:
            return m # target is in the middle
        if target < nums[m]:
            r = m-1 # search in the left half
        else:
            l = m+1 # search in the right half
    return -1 # target not found

הרחבת אלגוריתם חיפוש בינארי לצורך חיפוש במערך מסובב

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

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

כך נוכל להבטיח חיפוש עם סיבוכיות זמן של O(log N).

הקוד הבא מיישם את הפתרון:

def search_in_inverted_array(nums, target):
    l = 0  # left pointer
    r = len(nums) - 1  # right pointer
    while l <= r:
        m = (l + r) // 2  # the index at the middle
        if target == nums[m]:
            return m  # mid index
        # left half is ordered
        if nums[l] <= nums[m]:
            # if target within boundaries of the left half
            if nums[l] <= target <= nums[m]:
                r = m - 1  # search in the left half
            else:
                l = m + 1  # search in the right half
        # right half is ordered
        else:
            # if target within boundaries of the right half
            if nums[m] <= target <= nums[r]:
                l = m + 1  # search in the right half
            else:
                r = m - 1  # search in the left half
    return -1  # target not found

יעילות זמן ומקום

סיבוכיות זמן: O(log N) – מרחב החיפוש מצטמצם בחצי בכל איטרציה של הלולאה, ולכן הזמן הנדרש הוא לוגריתמי.

סיבוכיות מקום: O(1) – הפתרון לא צורך זיכרון נוסף.

סיכום

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

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

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

אתגר תכנותי: איסוף ערכי המקסימום בתוך חלון הזזה Sliding window maxima

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

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

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

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

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