חיפוש בינארי

חיפוש בינארי (ידוע גם בשם אריה במדבר) הוא אלגוריתם לחיפוש, כלומר למציאת מקומו של איבר במערך ממוין. סוג החיפוש הנ״ל נקרא "בינארי" מכיוון שהאלגוריתם מחפש או בצד הימני או בצד השמאלי של המערך. ישנם רק 2 מקרים אפשריים, ולכן החיפוש "בינארי".

מטרה

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

תיאור האלגוריתם

עקרון

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

מימוש מילולי

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

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

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

שפת C

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

 int BinarySearch(int* a,int x, int left, int right)
 {
   if(left>right)
     return -1;

   int middle = (left right)/2;
   if(a[middle]==x)
     return middle;

   if(x<a[middle])
     return BinarySearch(a,x,left,middle-1);

   return BinarySearch(a,x,middle 1,right);
 }

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

 int BinarySearch(int* a,int x, int left, int right)
 {
   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. סדרה זו ידועה בשם סדרת פיבונאצ'י, אך לצורך העניין כל שמעניין אותנו הוא עובדת היותם של מספרים אלה מסודרים בסדר עולה. כעת נסתכל על מערך שמכיל סדרה זו.

0	1	2	3	4	5	6	7	8	9
1	1	2	3	5	8	13	21	34	55

שימו לב שהערכים בשורה העליונה הם המקומות במערך (Indexes), ("מחשב" מתחיל לספור מהספרה אפס ולכן המיקום/האינדקס הראשון הוא 0 ולא 1) ואילו הערכים בשורה התחתונה הם הנתונים הנשמרים במערך (Values). לדוגמה, במקום השלישי במערך (אינדקס 2) שמור הערך 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 ואכן זה נכון.

מקורות השמות

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

לקריאה נוספת

קישורים חיצוניים

מדיה וקבצים בנושא חיפוש בינארי בוויקישיתוף

איך תופסים אריה במדבר? באתר הבלוג "לא מדויק".
חיפוש בינארי, באתר MathWorld (באנגלית)