אלגוריתמי חיפוש
הוצג| English | משמעות |
|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | חיפוש ליניארי |
| binary search/ˈbaɪnəri sɜːtʃ/ | חיפוש בינארי |
עשרים שאלות למיליון שמות
- טלפון מכיל מיליון שמות. אם תבדוק אותם אחד אחרי השני, תצטרך כמחצית מיליון השוואות לפני שתמצא את זה שאתה מחפש.
- במקום זאת, פתח במרכז, קבע באיזה חלק השם נמצא, והשלך את החלק האחר. חזור על הפעולה. תגיע לכל שם ב-עשר השוואות.
- מחצית מיליון מול עשר הוא לא רק חיסכון; זו ההפרדה בין תוכנית שעובדת לבין תוכנית שאינה ניתנת לשימוש. והכל על משקל דבר אחד: הרשימה חייבת להיות מסודרת מראש.
- שיעור זה עוסק ב-חיפוש ליניארי וב-חיפוש בינארי, כיצד כל אחד מהם מתפקד, וכיצד לבחור ביניהם.
חיפוש ליניארי
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
- הוא הולך מהתחלה ומשווה כל אלמנט למטרה, ועוצר כאשר מוצא התאמה או מגיע לסוף.
- הוא עובד עם כל רשימה, מסודרת או לא, ועם כל מבנה שיכול להישפך.
- מקרה גרוע: המטרה היא האחרונה או שאינה קיימת, ולכן כל $n$ אלמנטים מושווים, כלומר $O(n)$. בממוצע, בערך חצי.
אחד אחד, מהתחלה
חיפוש ליניארי:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
חיפוש ליניארי אינו דורש הכנה ועובד על כל רשימה, ברעה O(n).
חיפוש ליניארי הוא הבחירה הטובה יותר כאשר הנתונים הם:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ללא סדר לניצול (או רשימה זעירה), חיפוש ליניארי נמנע מהעלות של סינון מקדים.
חיפוש בינארי
low ← 1 ; high ← n
WHILE low <= high DO
mid ← (low + high) DIV 2
IF A[mid] = target THEN
RETURN mid
ENDIF
IF A[mid] < target THEN
low ← mid + 1
ELSE high ← mid - 1
ENDWHILE
RETURN -1
- הוא דורש שהנתונים יהיו מסודרים. השוו את האלמנט האמצעי למטרה: אם יש התאמה, עצור; אם המטרה גדולה יותר, השלך את החלק התחתון; אחרת השלך את החלק העליון.
- כל השוואה מחצה את הטווח שנותר לחפש, ולכן מספר ההשוואות הוא $O(\log_2 n)$.
- לכן מיליון פריטים דורשים כ-20 השוואות: $2^{20}$ הוא מעט מעל מיליון.
אלגוריתמי חיפוש
חיפוש דו-סעפי מחצית את הטווח בכל צעד
חיפוש ליניארי בודק כל פריט; חיפוש דו-סעפי מחצית רשימה ממוינת — הרבה פחות השוואות.
המורכבות בזמן ברעה של חיפוש דו-סעפי היא:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
החציית הטווח בכל צעד נותנת מספר לוגריתמי של השוואות.
כמה השוואות בערך צריך חיפוש בינארי עבור מיליון פריטים מסודרים?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$\log_2(1\,000\,000) \approx 20$ — כ-20 השוואות.
חיפוש בינארי ניתן לשימוש בכל רשימה, מסודרת או לא.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הוא קובע איזו מחצית לדחות על ידי השוואה עם האלמנט באמצע, דבר שיש לו משמעות רק אם הנתונים במסדר.
חיפוש בינארי הוא O(log n) כי כל השוואה ____ את הטווח שנותר לחפש.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
עשרים חצייה מורידות מיליון לאחד, ולכן העובדה ש-2^20 מעט יותר ממיליון היא המספר שצריך לזכור.
דוגמה מפורטת: עקוב אחר חיפוש בינארי
- הרשימה המסודרת היא 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. עקוב אחר החיפוש עבור 23.
lowהוא 1,highהוא 10, ולכןmidהוא 5, והוא מכיל את 16. 16 קטן מ-23, ולכן השלך את החלק התחתון:lowהופך ל-6.low6,high10, ולכןmidהוא 8, המכיל 56. 56 גדול מ-23, ולכןhighהופך ל-7.low6,high7, ולכןmidהוא 6, המכיל 23. נמצא, בשלוש השוואות בעוד שחיפוש ליניארי דורש שישה.- הצג את
low,high,midואת הערך בכל שלב. רוב הנקודות נמצאות בניתוח ההתנהגות, לא בתשובה עצמה.
ברשימה המסודרת 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, כמה השוואות צריך חיפוש בינארי כדי למצוא את 23?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
אמצע 5 מכיל 16 (קטן מדי), אמצע 8 מכיל 56 (גדול מדי), אמצע 6 מכיל 23. חיפוש ליניארי היה לוקח שישה צעדים.
בחירה בין הפורמטים
| ליניארי | בינארי | |
|---|---|---|
| נתונים חייבים להיות מסודרים | לא | כן |
| השוואות, גרוע המקרה | $n$ | $\log_2 n$ |
| מיליון פריטים | עד 1,000,000 | כ-20 |
| מתאים | רשימות לא מסודרות או קטנות, רשימות מקשרות | מערכים מסודרים גדולים, מחוקקים באופן חוזר |
- סידור מראש עולה יותר מחיפוש ליניארי אחד, ולכן חיפוש בינארי משתלם רק כאשר הרשימה כבר מסודרת או שתיחודש חיפשים רבים עליה.
- לחיפוש בינארי נדרש גם גישה ישירה לאיבר האמצעי, שארשימה יש לה ואין לרשימה מקשרת.
דוגמה מפורטת: הנמנת בחירה
- תוכנית מחפש רשימה לא מסודרת של 50 רשומות פעם אחת. חיפוש ליניארי: סידור הרשימה תחילה יעלה הרבה יותר מ-50 ההשוואות שהחיפוש זקוק להן.
- תוכנית מחפש מערך מסודר של מיליון רשומות אלפים פעמים בשנייה. חיפוש בינארי: הנתונים כבר מסודרים וכל חיפוש עולה כ-20 השוואות במקום עד מיליון.
- תוכנית מחפש רשימה מקשרת. חיפוש ליניארי: חיפוש בינארי זקוק לקפוץ ישירות לאיבר האמצעי, והרשימה המקשרת יכולה להתבצע רק מהתחלה.
- קרא לשם האלגוריתם, ולאחר מכן לציון המאפיין של ה-נתונים שמחליט על בחירתו.
התאם כל שיטה לחיפוש עם העובדות המפתח שלה.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
חיפוש בינארי מהיר הרבה יותר (O(log n)) אך רק על נתונים מסודרים; חיפוש ליניארי עובד בכל מקום ב-O(n).
מתי חיפוש ליניארי הוא הבחירה הטובה יותר? סמן את כולם החלופות הנכונות.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
המקרה האחרון הוא בדיוק שם בו חיפוש בינארי מנצח. הסינון מראש עולה יותר מחיפוש ליניארי אחד, ולכן הוא משתלם רק לאחר מספר רב של חילושים.
עלות שמירת המסמך במצב מסודר
- חיפוש בינארי זמין רק ברשימה מסודרת, וסידור זה אינו חינם. שאלה שדורשת ממך להצדיק בחירה היא דורשת ממך לחשב את המחיר שלה.
- אם הנתונים מחוקקים בתדירות וגרושים לעיתים נדירות, סדר אותם פעם אחת וכל חיפוש אחר יהיה $\log_2 n$. זה המקרה עבור מילון או טבלת חיפוש.
- אם הנתונים מתעדכנים באופן מתמיד, כל הכנסה חייבת לשמור על הסדר, מה שעולה בהזזה של האיברים הבאים. חיפוש ליניארי על נתונים לא מסודרים עשוי אז להיות הזול בסך הכל.
- מספרים הופכים את הטענה למلموسة: מיליון רשומות דורשות עד מיליון השוואות ליניאריות, אך רק 20 בחיפוש בינארי, מכיוון ש$2^{20} > 10^6$.
- לכן התשובה המסומנת מציינת שתי החלקים: כמה פעמים החיפוש מתבצע וכמה פעמים הנתונים משתנים.
סדרו את ההצדקה לבחירת אלגוריתם החיפוש.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
שאלת הצדקה דורשת את האיזון בין היתרונות והחסרונות, ולא את המנצח. חיפוש בינארי ברשימה משתנה באופן מתמיד יכול לעלות בסך הכל יותר מחיפוש ליניארי.
סימונים נופלים מהיד
- חיפוש בריבוי דורש נתונים מסודרים. אמירה כי "זה מהיר יותר" ללא תנאי זהה מאבדת נקודה.
- בשלבים כל אחד חוצה את הטווח בפי, ומכאן נובע ה$\log_2 n$. יש לתת את ההסבר, ולא רק את הסימון.
- שני סוגי החיפוש חייבים יכולת לדווח על אי-מציאה, וזאת המטרה של ה
-1ותנאי הלולאה. - לחיפוש בריבוי נדרש גישה ישירה, ולכן הוא אינו מתאים לרשימה מקושרת אף אם הרשימה מסודרת.
הבנתך מושלמת
- חיפוש ליניארי משווה כל אלמנט בהתחלה, עובד על כל רשימה, והוא $O(n)$
- חיפוש בריבוי דורש נתונים מסודרים עם גישה ישירה, משווה את האמצע וחוצה את הטווח בכל פעם, מה שמניב $O(\log_2 n)$: כ-20 השוואות למיליון פריטים
- לעקוב אחרי חיפוש בריבוי על ידי הצגת
low,high,midוערך בכל צעד - לבחור מהנתונים: לא מסודר, קטן או רשימה מקושרת מצביעים על ליניארי; גדול, מסודר וחוקר לעיתים קרובות מצביעים על בריבוי