חיפוש בינארי

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

מטרה

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

עקרון

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

שפת 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 = 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
}

חישוב הסיבוכיות

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

מקורות השמות

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