אלגוריתמי חיפוש
הוצג| English | משמעות |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | חיפוש |
| linear search/ˈlɪnɪə sɜːtʃ/ | חיפוש ליניארי |
| binary search/ˈbaɪnəri sɜːtʃ/ | חיפוש בייני |
| sorted/ˈsɔːtɪd/ | ממוין |
מציאת ערך
- חיפוש פירונו מציאת ערך מטרה באוסף נתונים.
- שני אלגוריתמים סטנדרטיים: חיפוש ליניארי וחיפוש בינארי.
- שניהם מחזירים את האינדקס בו נמצא המטרה — או אות "לא נמצא" (לרוב
-1). - איזה מהם להשתמש בו תלוי אם הנתונים מוצגים בסדר.
חיפוש ליניארי
- בדוק כל אלמנט מהתחלה, אחד אחר השני, עד שתמצא את המטרה.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- עובד על כל מערך — מסודר או לא.
- מקרה גרוע: הוא בוחן כל האלמנטים (
nבדיקות).
חיפוש בינארי
- דורש מערך מסודר. בדוק את האלמנט באמצע בכל פעם.
- אם האמצע הוא המטרה, סיימת. אם המטרה קטנה יותר, חפש בחצי השמאלי; אם גדולה יותר, בחצי הימני.
- בשלב כללי מתחצית הטווח שנותר לחפוש.
- מהיר משמעותית במערות מסודרים גדולים — כ-
log₂ nבדיקות, ולאn.
למה חיפוש בינארי מהיר
- חיפוש ליניארי של מיליון פריטים: עד למיליון בדיקות.
- חיפוש בינארי של מיליון פריטים מסודרים: כ-20 בדיקות.
- התנאי: המערך חייב להיות כבר מסודר.
- חיצון חוזר הוא הרעיון המרכזי מאחורי
O(log n).
חיפוש בינארי עובד רק על מערך מסודר — הפעלתו על נתונים לא מסודרים תניב תוצאות שגויות. הוא גם משווה לאמצע ומפסל חצי מטווח בכל שלב; בעוד שחיפוש ליניארי משווה מהתחלה ומפסל רק אלמנט אחד. אם אינך בטוח שהנתונים מסודרים, עליך להשתמש בחיפוש ליניארי (או לסדר קודם).
חיפוש בינארי עבור 7 ב-[1, 3, 5, 7, 9]:
- האמצע הוא ⟨
5⟩ (אינדקס 2). 7 > 5, לכן נחפש בחצי הימני. - החצי הימני הוא
[7, 9]; האמצע הוא7. נמצא במדד 3. - שתי בדיקות במקום ארבע — הטווח התחצית בכל פעם.
חיפוש ליניארי בודק אלמנטים מהתחלה (עובד על כל מערך, עד ל-n בדיקות). חיפוש בינארי דורש מערך מסודר, משווה לאמצע, ומתחצית את טווח החיפוש בכל שלב (כ-log₂ n בדיקות). שניהם מחזירים את האינדקס שנמצא, או אות "לא נמצא" כמו ⟨-1⟩.
חיפוש ליניארי לעומת חיפוש בינארי
חיפוש בינארי מחצית את הטווח הממוין בכל צעד.
חיפוש ליניארי...
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
הוא משווה לאלמנט האמצעי ושומר חצי מהנתונים.
חיפוש בלוגי ב-[1,3,5,7,9] עבור 7: כמה השוואות (באמצע בכל פעם)?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
השוואה ל-5, ולאחר מכן ל-7 — שתי השוואות.
חיפוש בלוגי נותן תוצאות נכונות במערך לא מסודר.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הוא מסתמך על הסדר; נתונים לא מסודרים מפסלים אותו.
התאם כל שיטה לחיפוש לתכונה שלה.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
חיפוש ליניארי הוא אוניברסלי אך איטי יותר; חיפוש בלוגי מהיר אך דורש סדר.