תחי ישראל - אין לנו ארץ אחרת

תחי ישראל -אין לנו ארץ אחרת

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

מחבר:
בתאריך:

האתגר

נתון מערך מספרים `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

מדריך: חיפוש בינארי במערך מסובב rotated array

 

הצעה לפתרון

כיוון שהדרישה היא שהאלגוריתם ירוץ בסיבוכיות זמן של 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 כוכבים

 

 

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

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

שימו לב! הסקריפטים במדריכים מיועדים למטרות לימוד בלבד. כשאתם עובדים על הפרויקטים שלכם אתם צריכים להשתמש בספריות וסביבות פיתוח מוכחות, מהירות ובטוחות.

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

השימוש שלך באתר מהווה ראייה להסכמתך עם הכללים והתקנות שנוסחו בהסכם תנאי השימוש.

הוסף תגובה חדשה

 

 

ענה על השאלה הפשוטה הבאה כתנאי להוספת תגובה:

דג למים הוא כמו ציפור ל...?