Search in Rotated Sorted Array
רשימה של מספרים שלמים שונים סודרה בסדר עולה ואז סובבה: מספר כלשהו של איברים, אולי אפס, נלקחו מההתחלה והועברו לסוף באותו סדר. לדוגמה, סיבוב של [2, 5, 8, 11, 15, 19, 23] ב־4 מקומות נותן [15, 19, 23, 2, 5, 8, 11]. נתונות לך הרשימה המסובבת nums והמספר השלם target. החזר את האינדקס של target ב־nums, בספירה החל מ־0, או -1 אם הוא לא נמצא שם, בזמן O(log n).
פונקציה
- numsinteger-array
- הרשימה המסובבת והממוינת של מספרים שלמים שונים
- targetinteger
- הערך שיש לחפש
- מחזירהinteger
- האינדקס של target בתוך nums, או -1 אם הוא חסר
אילוצים
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- כל הערכים ב־
numsשונים זה מזה. numsהיא רשימה עולה שסובבה ב־kכלשהו, כאשר0 ≤ k < nums.length;k = 0משאיר אותה ללא סיבוב.
דוגמאות
- קלט
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- פלט
- 4
- הסבר
- האמצע הראשון, באינדקס 3, מכיל 2, לכן החצי הימני
[2, 5, 8, 11]ממוין ומכיל 5. האמצע הבא, באינדקס 5, מכיל 8; החלק השמאלי הממוין[5, 8]מכיל 5, מה שמוביל לאינדקס 4.
- קלט
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- פלט
- -1
- הסבר
- 65 אמור להיות בין 60 ל־70, ואף איבר אינו מכיל אותו. האמצעי הראשון, 70, מציב את 65 בתוך החלק השמאלי הממויין
[40, 50, 60, 70], והטווח מצטמצם שם עד שהוא מתרוקן.
- קלט
- nums = [8, 13, 21, 1, 3, 5]target = 13
- פלט
- 1
- הסבר
- האיבר האמצעי הראשון, באינדקס 2, מכיל את הערך 21. החלק השמאלי
[8, 13, 21]ממוין, ו-13 נמצא בין 8 ל-21, לכן החלק הימני נזרק. לאחר מכן החיפוש מוצא את 13 באינדקס 1.
שאלת המשך
אם nums עשוי להכיל כפילויות, שום אלגוריתם לא יכול להבטיח O(log n). האם תוכל להוכיח זאת באמצעות רשימה מסובבת של 1-ים שמסתירה 0 יחיד?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
בחר כל אינדקס אמצעי והסתכל על שני החצאים שמשני צדדיו. הסיבוב יצר מקום אחד שבו הערכים יורדים, מהגדול ביותר לקטן ביותר. האם שני החצאים יכולים להכיל את הירידה הזאת?
לפחות חצי אחד תמיד ממוין, והשוואה בין
nums[lo]ל־nums[mid]תגלה לך איזה מהם. עבור חצי ממוין אפשר לבדוק בצעד אחד אםtargetנמצא בין הערך הראשון לערך האחרון שלו.השאר את
loואתhiסביב החלק שעשוי עדיין להכיל אתtarget. בכל שלב, אם טווח הערכים של החצי הממויין מכיל אתtarget, השאר את החצי הזה; אחרת, השאר את החצי השני. עצור כשתמצא אתtargetאו כשהטווח ריק.
פתרון
רשימה ממוינת שעברה סיבוב מורכבת משני רצפים ממוינים: [15, 19, 23] ולאחר מכן [2, 5, 8, 11]. השוואת target לערך האמצעי כבר לא אומרת לך באיזה צד הוא נמצא. אבל בכל מקום שבו תחלק את הרשימה, לפחות חצי אחד יהיה ממוין, והשוואה אחת תגלה לך אם target יכול להימצא באותו חצי.
סרוק כל רכיב
האינטואיציה
בדקו כל אינדקס והחזירו את הראשון שהערך שלו שווה ל־target, או את -1 לאחר הלולאה. היא קוראת כל איבר, ולכן היא נכונה עבור כל רשימה. היא מתעלמת משתי הריצות הממוינות: 5000 איברים דורשים עד 5000 השוואות, בעוד שחיפוש בינארי דורש 13.
אלגוריתם
- עבור כל אינדקס
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. גם nums[k..n-1] וגם nums[0..k-1] ממוינים, וכל ערך בריצה הראשונה גדול מכל ערך בריצה השנייה. ברגע שיודעים את k, השוואה של target עם nums[k] ועם nums[n-1] קובעת באיזו ריצה לחפש, וחיפוש בינארי רגיל משלים את המשימה.
כדי למצוא את k, משווים את הערך האמצעי עם nums[hi]. אם nums[mid] > nums[hi], הערכים יורדים איפשהו אחרי mid, ולכן המינימום נמצא מימינו. אחרת, הערכים ב־nums[mid..hi] עולים ללא ירידה, ולכן המינימום נמצא ב־mid או לפניו. בדוגמה הראשונה הערכים האמצעיים הם 2, 19 ו־23, ולכן מתקבל k = 3, והערך 5 נמצא בין nums[3] = 2 ל־nums[6] = 11. שני חיפושים בינאריים דורשים בערך 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. - החזר את האינדקס שנמצא, או
-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 מכיל את הירידה, והחצי השני ממוין. אם nums[lo] ≤ nums[mid], החצי השמאלי ממוין; אחרת, החצי הימני ממוין.
בחצי הממוין, בדיקת טווח בשני הקצוות שלו מראה אם target יכול להימצא בתוכו, למשל nums[lo] ≤ target < nums[mid] בצד שמאל. אם כן, חפשו שם; אם לא, target יכול להימצא רק בחצי השני. בכל שלב הטווח מצטמצם למחצית: לכל היותר 13 שלבים עבור 5000 איברים.
אלגוריתם
- הגדר
lo = 0ואתhi = n-1. - כל עוד
lo ≤ hi, חשב אתmidוהחזר אותו אםnums[mid]שווה ל-target. - אם
nums[lo] ≤ nums[mid], החצי השמאלי ממוין: הגדרhi = mid - 1כאשרnums[lo] ≤ target < nums[mid], אחרת הגדרlo = mid + 1. - אחרת, החצי הימני ממוין: הגדר
lo = mid + 1כאשרnums[mid] < target ≤ nums[hi], אחרת הגדר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מחזיר-1. - השוואת
targetעםnums[mid]תחילה. בדוגמה הראשונה עםtarget = 19, האיבר האמצעי 2 קטן יותר, ולכן החיפוש נע ימינה ומפספס את האינדקס 1. - בדיקת קצה אחד בלבד של החצי הממויין. ב־
[40, 50, 60, 70, 80, 10, 20]עםtarget = 80, התנאיtarget ≥ nums[lo]לבדו שולח את החיפוש אל[40, 50, 60, 70]. - ב־Rust, הביטוי
k - 1עלusizeגולש כלפי מטה כש־k = 0, כלומר ברשימה שלא עברה סיבוב. השתמשו בטווחים חצי פתוחים. - ב־Lua וב־R, החזרת המיקום המבוסס על אינדקס שמתחיל ב־1. החסירו 1.
שאלות נפוצות3
מהי סיבוכיות הזמן של חיפוש במערך ממוין שעבר סיבוב?
זמן O(log n) ומקום נוסף O(1). בכל שלב נשמרת מחצית אחת של הטווח, ולכן עבור 5000 איברים נדרשים לכל היותר 13 שלבים. גם מציאת נקודת הסיבוב תחילה היא O(log n), ודורשת בערך פי שניים שלבים.
האם האלגוריתם עובד כשהמערך מכיל ערכים כפולים?
לא כפי שזה כתוב. כאשר nums[lo], nums[mid] ו־nums[hi] שווים, אי אפשר להוכיח שאף אחד משני החצאים ממוינים. התיקון המקובל מקדם את lo באחד במקרה כזה, וכך שומר על נכונות התשובה, אך הופך את המקרה הגרוע ביותר ל־O(n).
האם כדאי למצוא תחילה את נקודת הסיבוב או לחפש במעבר אחד?
שתיהן פועלות בזמן O(log n). מציאת המינימום תחילה מפצלת את הבעיה לשני חיפושים בינאריים רגילים. החיפוש במעבר יחיד עושה את העבודה בלולאה אחת ובפחות צעדים, וזהו הפתרון שרוב המראיינים מצפים לו.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def search(nums, target):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
הפלט הצפוי
4