חיפוש בינארי – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
Earthei (שיחה | תרומות)
הרחבה
Earthei (שיחה | תרומות)
א
שורה 114:
שים לב שהערכים בשורה העליונה הם המקומות במערך (Indexes) ואילו הערכים בשורה התחתונה הם הנתונים הנשמרים במערך (Values). לדוגמה במקום השלישי במערך שמור הערך 2.
 
ננסה לחפש כעת, באמצעות אלגוריתם אריה במדבר, האם המספר 2 מופיע במערך. במערך עשרה איברים ולכן <math>\ n=10 </math>.
 
1. '''אמצע <- 2 / (תחילת_מערך + סוף_מערך)'''
שורה 120:
תחילת_מערך הוא מספורו של התא הראשון ובמקרה זה 1 ולו סוף_מערך הוא מספורו של התא האחרון, במקרה זה 10. 10+1=11 ואם נחלק ב-2 נקבל 5 (אם אנו מעגלים כלפי מטה). אמצע כעת יהיה שקול למספר 5.
 
2. '''אם מערך [אמצע] = ערך_מבוקש'''
 
ערכו של המערך במקום החמישי הוא 5 וזה לא שווה לערך המבוקש, 2. לכן נדלג על שלב זה ונמשיך מיד לכיוון ה"אחרת".
שורה 126:
3. '''אחרת,'''
 
: 3.1 '''אם מערך [אמצע] < ערך_מבוקש'''
: 5 אינו קטן מ-2 ולכן נמשיך אל עבר ה"אחרת" של תנאי זה.
 
: 5 אינו קטן מ-2 ולכן נמשיך אל עבר ה"אחרת" של תנאי זה.
 
: 3.2 '''אחרת,'''
:: 3.2.1 '''חיפוש_בינאריחיפוש בינארי (תחילת_מערך, אמצע, ערך_מבוקש)'''
 
:: משמע יש לשחזר את התהליך כולו אך הפעם סוף_מערך יהיה 5 ולא 10.
:: 3.2.1 '''חיפוש_בינארי (תחילת_מערך, אמצע, ערך_מבוקש)'''
 
:: משמע יש לשחזר את התהליך כולו אך הפעם סוף_מערך יהיה 5 ולא 10.
 
1. '''אמצע <- 2 / (תחילת_מערך + סוף_מערך)'''
שורה 140 ⟵ 137:
תחילת_מערך הוא מספורו של התא הראשון ובמקרה זה 1 ולו סוף_מערך הוא מספורו של התא האחרון, במקרה זה 5. 5+1=6 ואם נחלק ב-2 נקבל 3.
 
2. '''אם מערך [אמצע] = ערך_מבוקש'''
ערכו של המערך במקום השלישי הוא 2 וזהו בדיוק הערך שבקשנו ולכן נכנס לתנאי זה ונמלא אחר ההוראות שם.
 
: 2.1 '''החזר אמצע'''
: אנו מחזירים את המספר 3.
 
: אנו מחזירים את המספר 3.
 
האלגוריתם החזיר 3, משמע שהמספר 2 קיים במערך והוא נמצא בתא מספר 3 ואכן זה נכון.
 
==מקורות השמות==
השם "חיפוש בינארי" נובע מכך שהאלגוריתם בוחר בכל שלב לחפש באיבר שמחלק את תחום החיפוש לשני חלקים בגודל שווה. מקור השם "אריה במדבר" מגיע מבדיחה על הדרך שבה מחפש מתמטיקאי אריה במדבר: המתמטיקאי מסתכל על המדבר, מחלקו לשני חלקים ובודק היכן האריה. כעת הוא ניגש לחלק המתאים וחוזר על פעולתיו עד שהוא מגיע לאריה.
 
== לקריאה נוספת ==
* [[חיפוש אקספוננציאלי]]
* [[חיפוש אינטרפולציה]]
 
==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
[[קטגוריה:אלגוריתמי חיפוש]]