חיפוש בינארי
מתוך ויקיפדיה, האנציקלופדיה החופשית
חיפוש בינארי הוא אלגוריתם רקורסיבי למציאת מקומו של איבר במערך ממוין. לעיתים נקרא אלגוריתם זה גם אריה במדבר.
תוכן עניינים |
[עריכה] מוטיבציה
ברשותינו מערך ממויין בגודל 
שאיבריו ממוינים. ברצונינו למצוא את מקומו של איבר מסוים תוך ניצול מיון המערך. במעבר על כל אחד האיברים נמצא את מיקום האיבר בסיבוכיות 
. מציאת האיבר ביעילות גדולה יותר פירושו מציאתו בדרך בעלת סיבוכיות קטנה יותר. מסתבר שבעזרת שיטת החיפוש הבינארי נוכל למצוא את מיקום האיבר בסיבוכיות של 
.
[עריכה] תיאור האלגוריתם
[עריכה] עקרון
נסתכל על המערך שברשותינו. נלך אל האיבר האמצעי. אם איבר זה הוא האיבר המבוקש הרי שמצאנו את מה שחיפשנו ונסיים כאן. אם לא, נבדוק מה היחס בין האיברים. אם האיבר המבוקש קטן יותר מאיבר זה, נביט בחציו השמאלי של המערך. אם האיבר המבוקש גדול יותר, נביט בחציו הימני של המערך. זאת בהנחה שהאיבר השמאלי ביותר במערך הוא הקטן ביותר ולו הימני ביותר הוא הגדול ביותר. כעת נחזור על כל מה שעשינו עם תת-המערך שברשותינו. במקרה הגרוע ביותר בו באף אחד מהמקרים לא היה האיבר האמצעי האיבר אותו אנו מבקשים, נגיע לתת-מערך בעל איבר אחד ואיבר זה חייב להיות האיבר שלנו. מובן, שניתן להפעיל גם את האלגוריתם עבור מקרה בו אנו מחפשים מיקומו של איבר שלא בהכרח קיים במערך, אז נבדוק אם גודל המערך 1 ואם אכן זהו גודלו ואינו מכיל את האיבר אזי נחזיר כי האיבר אינו במערך.
[עריכה] מימוש מילולי
הנחות והבהרות: המערך ממוין כך שאיבר השמאלי ביותר הוא הקטן ביותר. האיבר המבוקש נמצא במערך. גישה למקום מסוים במערך תתבצע כך: מערך[מקום_מסוים]. השמת ערך במשתנה תתבצע על ידי הסימן <- (חץ) ולו בדיקת שוויון תתבצע על ידי הסימן = (שווה).
חיפוש_בינארי(תחילת_מערך, סוף_מערך, ערך_מבוקש)
- אמצע <- 2 / (תחילת_מערך + סוף_מערך)
- אם מערך[אמצע] = ערך_מבוקש
- החזר אמצע
- אחרת,
- אם מערך[אמצע] < ערך_מבוקש
- חיפוש_בינארי( אמצע, סוף_מערך, ערך_מבוקש)
- אחרת,
- חיפוש_בינארי(תחילת_מערך,אמצע, ערך_מבוקש)
- אם מערך[אמצע] < ערך_מבוקש
[עריכה] חישוב הסיבוכיות
בידינו מערך בגודל כלומר יש בו איברים. בכל איטרציה (הפעלת האלגוריתם) אנו מצמצמים את המערך פי 2, שכן אנו בטוחים שהאיבר אינו בחצי המערך השני ולכן אין אנו בודקים אותו יותר. לאחר איטרציה אחת יהיה גודל המערך 
, לאחר שתי איטרציות יהיה גודלו 
, לאחר שלוש איטרציות יהיה גודל המערך 
וכן הלאה. התהליך ייגמר במקרה הגרוע ביותר כאשר גודל המערך הינו 1. אם התהליך כולו יימשך 
איטרציות, יהיה גודל המערך 
. אנו דורשים שגודל זה יהיה 1 ולכן נדרוש 
. נוציא 
משני אגפי המשוואה ונקבל כי 
.
קיבלנו כי סיבוכיות התהליך הינה . כלומר מספר הפעולות שאנו עושים קטן משמעותית (לוגריתמית) ממספר איברי המערך!
[עריכה] דוגמת הרצה
נסתכל על מערך המספרים: 1,1,2,3,5,8,13,21,34,55. סדרה זו ידועה בשם סדרת פיבונאצ'י, אך לצורך העניין כל שמעניין אותנו הוא עובדת היותם של מספרים אלה מסודרים בסדר עולה. כעת נסתכל על מערך שמכיל סדרה זו.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
שים לב שהערכים בשורה העליונה הם המקומות במערך ולו הערכים בשורה התחתונה הינם הנתונים הנשמרים במערך. לדוגמה במקום השלישי במערך שמור הערך 2.
ננסה לחפש כעת, באמצעות אלגוריתם אריה במדבר, האם המספר 2 מופיע במערך. במערך עשרה איברים ולכן 
.
1. אמצע <- 2 / (תחילת_מערך + סוף_מערך)
תחילת_מערך הינו מספורו של התא הראשון ובמקרה זה 1 ולו סוף_מערך הוא מיספורו של התא האחרון, במקרה זה 10. 10+1=11 ואם נחלק ב-2 נקבל 5 (במידה ואנו מעגלים כלפי מטה). אמצע כעת יהיה שקול למספר 5.
2. אם מערך[אמצע] = ערך_מבוקש
ערכו של המערך במקום החמישי הוא 5 וזה לא שווה לערך המבוקש, 2. לכן נדלג על שלב זה ונמשיך מיד לכיוון ה"אחרת".
3. אחרת,
- 3.1 אם מערך[אמצע] < ערך_מבוקש
- 5 אינו קטן מ-2 ולכן נמשיך אל עבר ה"אחרת" של תנאי זה.
- 3.2 אחרת,
-
- 3.2.1 חיפוש_בינארי(תחילת_מערך,אמצע, ערך_מבוקש)
-
- משמע יש לשחזר את התהליך כולו אך הפעם סוף_מערך יהיה 5 ולא 10.
1. אמצע <- 2 / (תחילת_מערך + סוף_מערך)
תחילת_מערך הינו מספורו של התא הראשון ובמקרה זה 1 ולו סוף_מערך הוא מיספורו של התא האחרון, במקרה זה 5. 5+1=6 ואם נחלק ב-2 נקבל 3.
2. אם מערך[אמצע] = ערך_מבוקש ערכו של המערך במקום השלישי הוא 2 וזהו בדיוק הערך שבקשנו ולכן נכנס לתנאי זה ונמלא אחר ההוראות שם.
- 2.1 החזר אמצע
- אנו מחזירים את המספר 3.
האלגוריתם החזיר 3, משמע שהמספר 2 קיים במערך והוא נמצא בתא מספר 3 ואכן זה נכון.
[עריכה] מקורות השמות
אלגוריתם זה דומה מאוד לשיטת חיפוש איבר בעץ חיפוש בינארי וכנראה שמכאן השם "חיפוש בינארי". מקור השם "אריה במדבר" כנראה נובע מדימוי הדרך בה מחפש מתמטיקאי אריה במדבר. המתמטיקאי מסתכל על המדבר, מחלקו לשני חלקים ובודק היכן האריה. כעת הוא ניגש לחלק המתאים וחוזר על פעולתיו עד אשר מגיע לאריה (כמובן ששיטה זו איננה מומלצת לחיפוש מעשי של אריה במדבר).
