Search in Rotated Sorted Array

Q: מהי סיבוכיות הזמן של חיפוש במערך ממוין שעבר סיבוב?

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

Q: איך יודעים איזה חצי של מערך מסובב ממוין?

השוו בין nums[lo] לבין nums[mid] . הערכים יורדים פעם אחת בלבד בכל הרשימה. אם nums[lo] ≤ nums[mid] , הירידה אינה בין lo ל־ mid , ולכן החצי השמאלי ממוין. אחרת, הירידה נמצאת בחצי השמאלי, כלומר בחצי הימני, מ־ mid עד hi , אין ירידה והוא ממוין.

Q: האם האלגוריתם עובד כשהמערך מכיל ערכים כפולים?

לא כפי שנכתב. ב- [1, 0, 1, 1, 1] , הערכים של nums[lo] , nums[mid] ו- nums[hi] כולם 1, ולכן אי אפשר להוכיח שאף אחד משני החצאים ממוינים. הפתרון המקובל הוא לקדם את lo באחד כאשר nums[lo] , nums[mid] ו- nums[hi] שווים, וכך התשובה נשארת נכונה, אך במקרה הגרוע הסיבוכיות היא O(n) .

Q: האם כדאי למצוא קודם את נקודת הסיבוב או לחפש במעבר אחד?

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

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

+10

רשימה של מספרים שלמים שונים סודרה בסדר עולה ואז סובבה: מספר כלשהו של איברים, ייתכן שאפס, נלקחו מתחילתה והועברו לסופה באותו סדר. לדוגמה, סיבוב של [2, 5, 8, 11, 15, 19, 23] ב־4 מקומות נותן את [15, 19, 23, 2, 5, 8, 11]. מקבלים את הרשימה המסובבת nums ואת המספר השלם target. יש להחזיר את האינדקס של target ב־nums, בספירה שמתחילה מ־0, או -1 אם הוא לא נמצא בה, בזמן O(log n).

פונקציה

search(nums: integer-array, target: integer) → integer

numsinteger-array: הרשימה המסובבת של מספרים שלמים שונים
targetinteger: הערך שיש לחפש
מחזירהinteger: האינדקס של target בתוך nums, או ‎-1 אם הוא חסר

אילוצים

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i], target ≤ 10⁴
כל הערכים ב־nums שונים זה מזה.
nums היא רשימה עולה שסובבה ב־k כלשהו, כאשר 0 ≤ k < nums.length; אם k = 0, היא נשארת ללא סיבוב.

דוגמאות

קלט: nums = [15, 19, 23, 2, 5, 8, 11]target = 5
פלט: 4
הסבר: 5 נמצא באינדקס 4. האמצעי הראשון, אינדקס 3, מכיל 2, לכן החצי הימני [2, 5, 8, 11] הוא החלק הממויין, ו-5 נמצא בין 2 ל-11. האמצעי הבא, אינדקס 5, מכיל 8; החלק השמאלי הממויין [5, 8] מכיל את 5, מה שמוביל לאינדקס 4.

קלט: nums = [40, 50, 60, 70, 10, 20, 30]target = 65
פלט: -1
הסבר: 65 היה אמור להימצא בין 60 ל־70, ואף איבר לא מכיל אותו. האמצע הראשון, 70 באינדקס 3, מציב את 65 בתוך החלק השמאלי הממויין [40, 50, 60, 70]. הטווח מצטמצם בתוך הרצף הזה עד שהוא מתרוקן, ולכן הפונקציה מחזירה -1.

קלט: nums = [8, 13, 21, 1, 3, 5]target = 13
פלט: 1
הסבר: האיבר האמצעי הראשון, באינדקס 2, מכיל 21. החלק השמאלי [8, 13, 21] ממוין, ו־13 נמצא בין 8 ל־21, לכן כל החלק הימני מושלך. לאחר מכן החיפוש מוצא את 13 באינדקס 1.

+23 בדיקות נסתרות בשליחה

שאלת המשך

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

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

רשימה ממוינת מסובבת מורכבת משני מקטעים ממוינים המוצבים בזה אחר זה: [15, 19, 23] ואז [2, 5, 8, 11]. חיפוש בינארי רגיל נכשל בה, משום שהשוואת target לערך האמצעי כבר לא מגלה לך באיזה צד נמצא target. הפתרון מבוסס על עובדה אחת: בכל מקום שבו תחלק את הרשימה, לפחות אחד משני החצאים יהיה ממוין במלואו, ובחצי ממוין אפשר לדעת בהשוואה אחת אם target יכול להימצא בו.

סרוק כל רכיב

האינטואיציה

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

היא מתעלמת מכל מה שהבעיה אומרת לך. הרשימה מורכבת משני מקטעים ממוינים, ובכל זאת הסריקה קוראת עד 5000 איברים, בעוד שחיפוש בינארי דורש כ־13 השוואות. הפער גדל עם הקלט: מיליון איברים עולים מיליון השוואות, לעומת כ־20. המשימה דורשת O(log n), ולכן זו נקודת הבסיס שממנה צריך להשתפר, לא התשובה.

אלגוריתם

עבור כל אינדקס i מ־0 עד n-1, השווה בין nums[i] לבין target.
אם הם שווים, החזר את i.
לאחר הלולאה, החזר את -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

מצא את נקודת הסיבוב, ואז בצע חיפוש בינארי

האינטואיציה

הרשימה המסובבת מורכבת משני מקטעים ממוינים, והשני מתחיל בערך הקטן ביותר. נסמן את האינדקס שלו ב־k. ברגע שיודעים את k, הבעיה הופכת לחיפוש בינארי רגיל: nums[k..n-1] ממוין ומכיל את הערכים מ־nums[k] עד nums[n-1], ו־nums[0..k-1] ממוין ומכיל את כל הערכים הגדולים יותר. השוואה אחת של target עם nums[k] ועם nums[n-1] קובעת באיזה מקטע לחפש.

כדי למצוא את k, מבצעים חיפוש בינארי על נקודת הירידה. משווים את הערך האמצעי לערך האחרון בטווח, nums[hi]. אם nums[mid] > nums[hi], הערכים יורדים איפשהו אחרי mid, ולכן הערך הקטן ביותר נמצא מימינו: קובעים lo = mid + 1. אחרת, הערכים ב־nums[mid..hi] עולים ללא נקודת ירידה, ולכן הערך הקטן ביותר נמצא ב־mid או לפניו: קובעים hi = mid, ומשאירים את mid בטווח. כש־lo מגיע ל־hi, האינדקס הזה הוא k.

נעקוב אחר הדוגמה הראשונה, [15, 19, 23, 2, 5, 8, 11] עם target = 5. הערך האמצעי 2 אינו גדול מ־11, ולכן hi הופך ל־3; לאחר מכן 19 גדול מ־2, ולכן lo הופך ל־2; לאחר מכן 23 גדול מ־2, ולכן lo הופך ל־3, ו־k = 3. מכיוון ש־5 נמצא בין nums[3] = 2 לבין nums[6] = 11, מחפשים באינדקסים 3 עד 6, שם החיפוש הבינארי מוצא את 5 באינדקס 4. העלות של שני חיפושים בינאריים היא בערך 2 log2 n צעדים.

אלגוריתם

הגדר lo = 0 ואת hi = n-1. כל עוד lo < hi, חשב את mid; אם nums[mid] > nums[hi], הגדר lo = mid + 1, אחרת הגדר hi = mid.
קרא לאינדקס הסופי k: הוא מכיל את הערך הקטן ביותר.
אם nums[k] ≤ target ≤ nums[n-1], חפש באינדקסים k עד n-1; אחרת חפש באינדקסים 0 עד k-1.
הפעל חיפוש בינארי רגיל בטווח הזה והחזר את האינדקס של target, או -1 אם הטווח מתרוקן.

def search(nums, target):
    n = len(nums)
    # 1. Find k, the index of the smallest value, where the second run starts.
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the drop is right of mid
        else:
            hi = mid      # mid is in the low run: the minimum is at mid or left of it
    k = lo
    # 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
    if nums[k] <= target <= nums[n - 1]:
        lo, hi = k, n - 1
    else:
        lo, hi = 0, k - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

חיפוש בינארי אחד בחצי הממויין

האינטואיציה

אין צורך לדעת היכן נמצאת נקודת הסיבוב. שמור על ההבטחה הרגילה של חיפוש בינארי: אם target נמצא ברשימה, האינדקס שלו נמצא בין lo ל-hi. בדוק את האינדקס האמצעי mid. הערכים יורדים פעם אחת בלבד בכל הרשימה, ולכן הירידה נמצאת לכל היותר באחד משני החצאים שמשני צדי mid, והחצי האחר ממוין.

מצא את החצי הממוין באמצעות השוואה אחת. אם nums[lo] ≤ nums[mid], בחצי השמאלי nums[lo..mid] אין ירידה והוא ממוין. מכיוון שכבר ידוע לך ש-nums[mid] אינו target, target יכול להיות בחצי הזה רק אם nums[lo] ≤ target < nums[mid]. אם כן, קבע hi = mid - 1; אם לא, target יכול להיות רק בחצי האחר, ולכן קבע lo = mid + 1. כאשר nums[lo] > nums[mid], הירידה נמצאת משמאל, החצי הימני nums[mid..hi] ממוין, והבדיקה ההפוכה nums[mid] < target ≤ nums[hi] היא שקובעת. אינך מסיק מסקנות ישירות על החצי הלא ממוין: target נמצא בו בדיוק כשהוא לא יכול להיות בחצי הממוין.

עקוב אחר הדוגמה הראשונה, [15, 19, 23, 2, 5, 8, 11] עם target = 5. לטווח שבין 0 ל-6 יש נקודת אמצע 3, והערך בה הוא 2. מכיוון ש-15 גדול מ-2, החצי הימני [2, 5, 8, 11] ממוין, ו-5 נמצא בו, ולכן lo הופך ל-4. לטווח שבין 4 ל-6 יש נקודת אמצע 5, והערך בה הוא 8. כעת nums[4] = 5 ≤ 8, החצי השמאלי [5, 8] ממוין ומכיל את 5, ולכן hi הופך ל-4. באינדקס 4 נמצא 5: החזר 4.

בכל שלב הטווח נחצה, כמו בחיפוש בינארי רגיל, ולכן הלולאה רצה לכל היותר בערך log2(n) + 1 פעמים: 13 צעדים עבור 5000 איברים, עם שני אינדקסים של זיכרון נוסף.

אלגוריתם

הגדר את lo = 0 ואת hi = n-1.
כל עוד lo ≤ hi, חשב את mid. אם nums[mid] שווה ל-target, החזר את mid.
אם nums[lo] ≤ nums[mid], החצי השמאלי ממוין: אם nums[lo] ≤ target < nums[mid] הגדר את hi = mid - 1, אחרת הגדר את lo = mid + 1.
אחרת החצי הימני ממוין: אם nums[mid] < target ≤ nums[hi] הגדר את lo = mid + 1, אחרת הגדר את hi = mid - 1.
כשהלולאה מסתיימת, החזר את -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            # nums[lo..mid] is sorted: target is in it only if it fits its range
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # nums[mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

מלכודות ומקרי קצה

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

כתיבת nums[lo] < nums[mid] במקום ≤. כשנותרים שני איברים, mid שווה ל-lo, והחצי השמאלי מכיל איבר אחד, ולכן הוא ממויין. עם הבדיקה המחמירה, [9, 4] ו-target = 4 גורמים להתייחסות אל [9, 4] כאל החצי הימני הממויין, לחיפוש 4 מחוץ לטווח שבין 9 ל-4, ולהחזרת -1.
השוואת target ל-nums[mid] תחילה, כמו בחיפוש בינארי רגיל. ב-[15, 19, 23, 2, 5, 8, 11] כאשר target = 19, הערך האמצעי 2 קטן מ-19, ולכן החיפוש נע ימינה ולעולם אינו מגיע לאינדקס 1.
בדיקת קצה אחד בלבד של החצי הממויין. ב-[40, 50, 60, 70, 80, 10, 20] כאשר target = 80, הערך האמצעי הוא 70 והחצי השמאלי [40, 50, 60, 70] ממויין. הבדיקה target ≥ nums[lo] לבדה שולחת את החיפוש שמאלה, כי 80 גדול מ-40, אבל 80 גדול גם מ-70, ולכן הוא נמצא בחצי הימני. בדקו את שני הקצוות.
שכחה של המקרה הלא מסובב בגישה הדו-שלבית. כאשר k = 0, הריצה השנייה ריקה והטווח שלה הוא 0 עד -1. זה בסדר עם אינדקסים עם סימן, אבל עם אינדקסים ללא סימן (usize של Rust), הביטוי k - 1 גורם לגלישה כלפי מטה, ולכן הקוד ב-Rust משתמש בטווחים חצי פתוחים.
החזרת המיקום עצמו ב-Lua וב-R. הרשימות שלהן מתחילות ב-1, ולכן יש להפחית 1 לפני ההחזרה.

שאלות נפוצות4

מהי סיבוכיות הזמן של חיפוש במערך ממוין שעבר סיבוב?

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

איך יודעים איזה חצי של מערך מסובב ממוין?

השוו בין nums[lo] לבין nums[mid]. הערכים יורדים פעם אחת בלבד בכל הרשימה. אם nums[lo] ≤ nums[mid], הירידה אינה בין lo ל־mid, ולכן החצי השמאלי ממוין. אחרת, הירידה נמצאת בחצי השמאלי, כלומר בחצי הימני, מ־mid עד hi, אין ירידה והוא ממוין.

האם האלגוריתם עובד כשהמערך מכיל ערכים כפולים?

לא כפי שנכתב. ב-[1, 0, 1, 1, 1], הערכים של nums[lo], nums[mid] ו-nums[hi] כולם 1, ולכן אי אפשר להוכיח שאף אחד משני החצאים ממוינים. הפתרון המקובל הוא לקדם את lo באחד כאשר nums[lo], nums[mid] ו-nums[hi] שווים, וכך התשובה נשארת נכונה, אך במקרה הגרוע הסיבוכיות היא O(n).

האם כדאי למצוא קודם את נקודת הסיבוב או לחפש במעבר אחד?

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

Python

def search(nums, target):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums = [15, 19, 23, 2, 5, 8, 11]
target = 5

צפוי

Search in Rotated Sorted Array

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

סרוק כל רכיב

מצא את נקודת הסיבוב, ואז בצע חיפוש בינארי

חיפוש בינארי אחד בחצי הממויין

מלכודות ומקרי קצה

שאלות נפוצות4

בעיות דומות