חיפוש בינארי
הוצג| English | משמעות |
|---|---|
| sorted/ˈsɔːtɪd/ | ממוין |
| Binary search/ˈbaɪnəri sɜːtʃ/ | חיפוש דו-לוגי |
| target/ˈtɑːɡɪt/ | מטרה |
| middle/ˈmɪdl/ | אמצע |
| comparison/kəmˈpærɪsn/ | השוואה |
| halves/hɑːvz/ | חצאים |
| linear search/ˈlɪnɪə sɜːtʃ/ | חיפוש ליניארי |
מציאת ערך מהיר ברשימה מסודרת
- חיפוש בינארי הוא דרך מהירה למצוא ערך מטרה ברשימה מסודרת.
- "מסודרת" פירושה שהערכים ממונים בסדר — מקטן לגדול, לדוגמה.
- זוהי דרך מהירה משמעותית מבדיקה של כל פריט בנפרד.
- אך יש לה דרישה מחמירה אחת.
חיפוש בינארי דורש נתונים מסודרים. ברשימה שאינה מסודרת, ייתכן שהאלגוריתם יעבור מעל הערך המטרה ויפסיד אותו. תמיד יש לסדר קודם לכן — או להשתמש בחיפוש אחר.
חיפוש בינרי ניתן לשימוש רק על נתונים ש-:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
על נתונים לא מסודרים ייתכן שלא ימצא את המטרה.
בדוק את האמצע, ואז חלק בשניים
- הרעיון פשוט: בדוק את האלמנט שב-אמצע. לאחר מכן:
- אם האמצע שווה למטרה, מצאת אותו;
- אם המטרה קטנה, חפש רק בחצי ה-שמאלי;
- אם המטרה גדולה, חפש רק בחצי ה-ימני.
חיפוש ליניארי לעומת חיפוש בינארי
חיפוש דו-סעפי מחצית את הטווח בכל צעד
חיפוש ליני בודק כל פריט; חיפוש בינרי מחלק רשימה מסודרת למחצה בכל השוואה, ולכן הוא דורש הרבה פחות צעדים.
אם המטרה גדולה מהאלמנט האמצעי, בחיפוש בינרי הבא נסתכל על:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
מטרה גדולה יותר חייבת להיות בחצי הימני (הגבוה).
כל השוואה בחיפוש בינרי ______ את החלק הנותר של הרשימה.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הכפלת למחצה בכל צעד היא הסיבה שהיא כל כך מהירה.
כמה בדיקות חיפוש בינרי נדרשות לערך עבור רשימה מסודרת של 1000 פריטים? (2^10 = 1024)
Difficulty 2/5 · 140 coins + a small bonus on first completion today
מכיוון ש-2^10 = 1024 ≥ 1000, כ-10 הכפלות למחצה מספיקות.
מדוע זה כל כך מהיר
- כל השוואה מחלק לשניים את חלק הרשימה שנותר.
- עבור 1000 פריטים, חיפוש ליניארי עשוי לדרוש עד 1000 בדיקות.
- לחיפוש בינארי דרושות עד כ-10 בדיקות, כי $2^{10} = 1024$.
- ככל שהרשימה גדולה יותר, כך היתרון רב יותר.
כמה השוואות נדרשות כדי למצוא את 14 ברשימה [2,5,8,11,14,17,20] בחיפוש בינרי?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
אמצע 11 → ימין; אמצע 17 → שמאל; אמצע 14 → נמצא: 3 השוואות.
ברשימה מסודרת גדולה, חיפוש בינארי דורש הרבה פחות השוואות מאשר חיפוש ליניארי.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הכפל של חצייה עוקפת בדיקה של כל פריט בנפרד.
לעומת חיפוש ליניארי
- חיפוש ליניארי בודק כל אלמנט אחד אחרי השני.
- חיפוש בינארי עוקף אותו ברשימות ממוינות גדולות על ידי חלוקה בשתיים בכל שלב.
חפש [2, 5, 8, 11, 14, 17, 20] עבור 14. האמצע הוא 11; 14 > 11 → חפש בחצי הימני [14, 17, 20]. האמצע הוא 17; 14 < 17 → חפש [14]. האמצע הוא 14 — נמצא ב-3 השוואות בלבד. חיפוש ליניארי היה לוקח 5.
חיפוש בינארי מוצא יעד ברשימה ממוינת על ידי בדיקת האמצע ושמירה רק על החצי שיכול להכיל אותו. כל השוואה משנה את הטווח לשני, ולכן 1000 פריטים דורשים ~10 בדיקות – הרבה פחות מ-1000 בדיקות של חיפוש ליניארי. זה עובד רק על נתונים ממוינים.