Binary Search
נתונה לך רשימה של מספרים שלמים nums, ממוינת בסדר עולה וללא ערכים שחוזרים על עצמם, ומספר שלם target. החזר את האינדקס של target בתוך nums, בספירה החל מ־0, או -1 אם הוא לא מופיע ברשימה. שאף לזמן ריצה של O(log n), כלומר אינך יכול לעבור על כל איבר ואיבר.
פונקציה
- numsinteger-array
- הרשימה הממוינת של מספרים שלמים ייחודיים
- targetinteger
- הערך שיש לחפש
- מחזירהinteger
- האינדקס של target בתוך nums, או -1 אם הוא חסר
אילוצים
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsממוינת בסדר עולה ממש, ולכן כל ערך מופיע פעם אחת.
דוגמאות
- קלט
- nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
- פלט
- 4
- הסבר
nums[4]הוא 9. החיפוש בודק את האינדקס 3 (הערך 4, קטן מדי), ואז את האינדקס 5 (הערך 15, גדול מדי), ואז את האינדקס 4, שבו הוא מוצא את 9.
- קלט
- nums = [1, 3, 5, 8, 13, 21]target = 10
- פלט
- -1
- הסבר
- 10 היה נמצא בין 8 ל־13, ואף אחד מהם אינו 10, ולכן הוא לא נמצא ברשימה. טווח החיפוש מצטמצם עד ש־
loעובר אתhi, והפונקציה מחזירה-1.
+15 בדיקות נסתרות בשליחה
שאלת המשך
אם הערכים ב-nums יכולים לחזור על עצמם, איך תחזיר את האינדקס הראשון של target, ועדיין בזמן O(log n)?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
הרשימה ממוינת. אם משווים את
targetלאיבר אחד באמצע, מה זה אומר לך על כל האיברים שנמצאים בצד אחד שלו?אם
nums[mid] < target, אזnums[mid]וכל מה שמשמאל לו קטנים מדי, ולכןtargetיכול להיות רק מימין. השוואה אחת מבטלת מחצית מהמועמדים.שמור על שני אינדקסים,
loו־hi, סביב החלק ברשימה שעדיין עשוי להכיל אתtarget. השווה לאיבר האמצעי, הזז אתloאו אתhiמעבר אליו, ועצור כשתמצא אתtargetאו כש־loיעבור אתhi.
פתרון
קריאה של האיברים בזה אחר זה מוצאת את target, אבל מתעלמת מהעובדה היחידה שהופכת את הבעיה למעניינת: הרשימה ממוינת. השוואה אחת לאיבר האמצעי מגלה לך באיזה חצי עדיין עשוי להימצא target, כך שבכל שלב אפשר לפסול חצי מהמועמדים. לכן, ברשימה של 10^4 איברים נדרשות לכל היותר 14 השוואות במקום 10000.
סרוק משמאל לימין
האינטואיציה
בדוק כל אינדקס לפי הסדר והחזר את הראשון שהערך שלו שווה ל־target. אם הלולאה מסתיימת בלי התאמה, target אינו נמצא ברשימה, לכן החזר -1. כל איבר מושווה פעם אחת, ולכן התשובה נכונה לכל רשימה, ממוינת או לא.
הכלליות הזאת היא הבעיה. רשימה של 10^4 איברים דורשת עד 10000 השוואות, והעבודה גדלה ביחס ישר ל־n. הסריקה אינה מנצלת את העובדה ש־nums ממוינת, ולכן אינה עומדת בחסם O(log n) שהמשימה דורשת. אפשר לעצור מוקדם ברגע שערך עובר את target, אבל במקרה הגרוע עדיין צריך לקרוא את הרשימה כולה.
אלגוריתם
- עבור כל אינדקס
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חיפוש בינארי עם שני אינדקסים
האינטואיציה
החזק שני אינדקסים, lo ו־hi, עם הבטחה אחת: אם target נמצא ברשימה, האינדקס שלו נמצא בין lo ל־hi, כולל הקצוות. בתחילת הדרך הטווח הוא הרשימה כולה, מ־0 ועד n-1. בדוק את האינדקס האמצעי mid. אם nums[mid] שווה ל־target, סיימת. אם הוא קטן יותר, מכיוון שהרשימה ממוינת כל איבר עד mid קטן גם הוא, ולכן העבר את lo אל mid + 1. אם הוא גדול יותר, העבר את hi אל mid - 1. ההבטחה עדיין מתקיימת אחרי כל אחת מההזזות.
עקוב אחר הדוגמה הראשונה, [-7, -2, 0, 4, 9, 15, 23] עם target = 9. לטווח מ־0 עד 6 יש אמצע 3, והערך בו הוא 4, קטן מדי, ולכן הטווח הופך ל־4 עד 6. האינדקס האמצעי שלו הוא 5, ובו נמצא 15, גדול מדי, ולכן הטווח הופך ל־4 עד 4. באינדקס 4 נמצא 9: החזר 4.
אם target חסר, הטווח ממשיך להצטמצם עד ש־lo עובר את hi. הטווח ריק כעת, ההבטחה אומרת ש־target אינו נמצא בשום מקום, ועליך להחזיר -1. בכל שלב הטווח נחצה, ולכן הלולאה רצה לכל היותר בערך log2(n) + 1 פעמים: 14 שלבים עבור 10^4 איברים. שני אינדקסים הם כל הזיכרון הנוסף הדרוש לך.
אלגוריתם
- הגדר את
lo = 0ואתhi = n-1. - כל עוד
lo ≤ hi, חשב אתmid = lo + (hi - lo) / 2. - אם
nums[mid]שווה ל־target, החזר אתmid. - אם
nums[mid] < target, הגדר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[mid] < target:
lo = mid + 1 # nums[mid] and everything left of it is too small
else:
hi = mid - 1 # nums[mid] and everything right of it is too big
return -1
מלכודות ומקרי קצה
חיפוש בינארי הוא קצר, וכמעט כל באג הוא טעות של אחד בגבולות הטווח.
- הרצה בלולאה עם
lo < hiכאשרhiמתחיל באינדקס האחרון. הלולאה נעצרת כשמועמד אחד עדיין לא נבדק, ולכןnums = [5]עםtarget = 5מחזיר-1. בטווח כולל, יש להריץ את הלולאה כל עודlo ≤ hi. - מעבר אל
lo = midאוhi = midבטווח כולל. כאשרloו-hiסמוכים,midשווה ל-loוהטווח לעולם אינו מצטמצם: לולאה אינסופית. כבר בדקת אתnums[mid], לכן יש לדלג מעבר אליו באמצעותmid + 1אוmid - 1. - חישוב
(lo + hi) / 2במספר שלם ברוחב קבוע. הסכום גולש ברגע שהאינדקסים עוברים בערך את10^9. המגבלות כאן נמוכות בהרבה, אבלlo + (hi - lo) / 2הוא הרגל בטוח. - החזרת
loכאשרtargetחסר. אחרי הלולאה,loהוא נקודת ההכנסה, שהיא אינדקס תקף ולא-1. - שכחת ההיסט ב-Lua וב-R. הרשימות שלהן מתחילות ב-1, לכן האינדקס שמחזירים הוא המיקום פחות 1.
שאלות נפוצות4
מהי סיבוכיות הזמן של חיפוש בינארי?
O(log n). כל השוואה מחלקת את הטווח שעדיין עשוי להכיל את היעד לשניים, ולכן לאחר k צעדים נשארים לכל היותר n / 2^k מועמדים. רשימה של 10^4 איברים דורשת לכל היותר 14 השוואות, ורשימה של 10^9 איברים לכל היותר 30. הגרסה האיטרטיבית משתמשת במקום נוסף של O(1).
למה חיפוש בינארי זקוק למערך ממוין?
השלב שמשליך מחצית מהרשימה מסתמך על הסדר. כאשר nums[mid] < target, המיון מבטיח שכל איבר שמשמאל ל־mid קטן גם הוא מ־target, ולכן אף אחד מהם לא יכול להתאים. ברשימה לא ממוינת, ההשוואה הזאת לא אומרת דבר על שאר האיברים, ועליך לבדוק את כולם.
האם חיפוש בינארי צריך להיות איטרטיבי או רקורסיבי?
שניהם נכונים ושניהם רצים בזמן O(log n). הגרסה הרקורסיבית קוראת לעצמה על חצי אחד ומשתמשת במרחב מחסנית של O(log n); הגרסה האיטרטיבית מזיזה את lo ואת hi בלולאה ומשתמשת ב־O(1). מראיינים בדרך כלל מצפים ללולאה, והיא מונעת כל מגבלת רקורסיה.
איך נמנעים מגלישה בחישוב האינדקס האמצעי?
כתוב mid = lo + (hi - lo) / 2 במקום (lo + hi) / 2. שתי הצורות מחזירות את אותו אינדקס, אבל בצורה השנייה מחברים תחילה שני אינדקסים, ובמספר שלם בן 32 סיביות הסכום הזה גולש ברגע שהאינדקסים עוברים בערך את 1.07 × 10^9. ב-Python וב-Ruby יש מספרים שלמים ללא גבול, ולכן הצורה המקוצרת בטוחה שם.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def search(nums, target):
# כתבו כאן את הקודמקרה 1
מקרה 2
קלט
nums = [-7, -2, 0, 4, 9, 15, 23] target = 9
צפוי
4