חיפוש בינארי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

חיפוש בינארי הוא אלגוריתם לחיפוש, כלומר למציאת מקומו של איבר במערך ממוין. לעתים נקרא אלגוריתם זה גם אריה במדבר.

מטרה[עריכת קוד מקור | עריכה]

נתון מערך ממוין בגודל \ n, ויש למצוא את מקומו של איבר מסוים במערך. במעבר סדרתי על איברי המערך נמצא את מיקום האיבר בסיבוכיות \ O(n). חיפוש בינארי מאפשר למצוא את מיקום האיבר בסיבוכיות של \ O(log(n)), כלומר ביעילות גבוהה במידה ניכרת.

תיאור האלגוריתם[עריכת קוד מקור | עריכה]

עקרון[עריכת קוד מקור | עריכה]

נבדוק את האיבר האמצעי שבמערך הנתון (הממוין כך שהאיבר השמאלי ביותר בו הוא הקטן ביותר, והאיבר הימני ביותר הוא הגדול ביותר במערך). אם האיבר האמצעי הוא האיבר המבוקש, הרי מצאנו את שחיפשנו ונסיים כאן. אם לא, נבדוק מה יחס הסדר בין האיברים. אם האיבר המבוקש קטן יותר מאיבר זה, נבחר את חציו השמאלי של המערך (שבו כל האיברים הקטנים מהאיבר האמצעי). אם האיבר המבוקש גדול יותר, נבחר את חציו הימני של המערך (שבו כל האיברים הגדולים מהאיבר האמצעי). כעת נחזור על כל מה שעשינו עם תת-המערך שבחרנו. במקרה הגרוע ביותר, שבו באף אחד מהמקרים לא היה האיבר האמצעי האיבר אותו אנו מבקשים, נגיע לתת-מערך בעל איבר אחד, שהוא האיבר המבוקש (או שנגיע למסקנה שהאיבר המבוקש כלל אינו נמצא במערך).

מימוש מילולי[עריכת קוד מקור | עריכה]

הנחות והבהרות: המערך ממוין כך שהאיבר השמאלי ביותר הוא הקטן ביותר. האיבר המבוקש נמצא במערך. גישה למקום מסוים במערך תתבצע כך: מערך[מקום_מסוים]. השמת ערך במשתנה תתבצע על ידי הסימן <- (חץ) ואילו בדיקת שוויון תתבצע על ידי הסימן = (שווה).

חיפוש_בינארי(תחילת_מערך, סוף_מערך, ערך_מבוקש)

  1. אמצע <- 2 / (תחילת_מערך + סוף_מערך)
  2. אם מערך[אמצע] = ערך_מבוקש
    1. החזר אמצע
  3. אחרת,
    1. אם מערך[אמצע] < ערך_מבוקש
      1. חיפוש_בינארי( אמצע + 1, סוף_מערך, ערך_מבוקש)
    2. אחרת,
      1. חיפוש_בינארי(תחילת_מערך, אמצע - 1, ערך_מבוקש)

שפת C[עריכת קוד מקור | עריכה]

מימוש רקורסיבי עבור מערך בגודל N:

   int BinarySearch(arr a,int x, int left, int right)
   {
       if(left>right)
           return -1;
       else
       {
           int middle=floor((left+right)/2);
           if(a[middle]==x)
               return middle;
           else
               if(x<a[middle])
                   return BinarySearch(a,x,left,middle-1);
               else
                   return BinarySearch(a,x,middle+1,right);
       }
   }

מימוש רגיל עבור מערך בגודל N:

   int BinarySearch(arr a,int x)
   {
       int left = 0;
       int right = N - 1;
       int middle;
       while (left <= right) {
           middle = floor((left + right)/2);
           if (a[middle] > x)
               right = middle - 1;
           else
               if (a[middle] < x)
                   left = middle + 1;
               else
                   return middle;
       }
       return -1;
   }

פסאודו- קוד[עריכת קוד מקור | עריכה]

מימוש רקורסיבי עבור מערך בגודל N:

   BinarySearch(a[0..N-1], x, left, right) {
       if (right < left)
           return not_found
       middle = floor((left + right)/2)
       if (a[middle] > x)
           return BinarySearch(a, x, left, middle-1)
       else if (a[middle] < x)
           return BinarySearch(a, x, middle+1, right)
       else
           return middle
   }

מימוש רגיל עבור מערך בגודל N:

   BinarySearch(a[0..N-1], x) {
       left = 0
       right = N - 1
       while (left <= right) {
           middle = floor((left + right)/2)
           if (a[middle] > x)
               right = middle - 1
           else if (a[middle] < x)
               left = middle + 1
           else
               return middle
       }
       return not_found
   }

חישוב הסיבוכיות[עריכת קוד מקור | עריכה]

בידינו מערך בגודל \ n כלומר יש בו \ n איברים. בכל איטרציה (הפעלת האלגוריתם) אנו מצמצמים את המערך לחצי מגודלו, שכן אנו בטוחים שהאיבר אינו בחצי המערך השני ולכן אין אנו בודקים אותו יותר. לאחר איטרציה אחת יהיה גודל המערך \frac{n}{2}, לאחר שתי איטרציות יהיה גודלו \frac{n}{2^2}, לאחר שלוש איטרציות יהיה גודל המערך \frac{n}{2^3} וכן הלאה. התהליך ייגמר במקרה הגרוע ביותר כאשר גודל המערך הינו 1. אם התהליך כולו יימשך \ k איטרציות, יהיה גודל המערך \frac{n}{2^k}. אנו דורשים שגודל זה יהיה 1 ולכן נדרוש \frac{n}{2^k} = 1. נוציא \ log משני אגפי המשוואה ונקבל כי \ k = log(n).

קיבלנו כי סיבוכיות התהליך היא \ O(log(n)). כלומר מספר הפעולות שאנו עושים קטן משמעותית (לוגריתמית) ממספר איברי המערך.

דוגמת הרצה[עריכת קוד מקור | עריכה]

נסתכל על מערך המספרים: 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

שים לב שהערכים בשורה העליונה הם המקומות במערך (Indexes) ואילו הערכים בשורה התחתונה הינם הנתונים הנשמרים במערך (Values). לדוגמה במקום השלישי במערך שמור הערך 2.

ננסה לחפש כעת, באמצעות אלגוריתם אריה במדבר, האם המספר 2 מופיע במערך. במערך עשרה איברים ולכן \ n=10 .


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 ואכן זה נכון.

מקורות השמות[עריכת קוד מקור | עריכה]

השם "חיפוש בינארי" נובע מכך שהאלגוריתם בוחר בכל שלב לחפש באיבר שמחלק את תחום החיפוש לשני חלקים בגודל שווה. מקור השם "אריה במדבר" מגיע מבדיחה על הדרך שבה מחפש מתמטיקאי אריה במדבר: המתמטיקאי מסתכל על המדבר, מחלקו לשני חלקים ובודק היכן האריה. כעת הוא ניגש לחלק המתאים וחוזר על פעולתיו עד שהוא מגיע לאריה.