חיפוש בינארי (Binary Search)

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

עקרון האלגוריתם

  • אם m>x (הערך שאנו מחפשים נמצא במשתנה x) נקרא לעצמנו (רקורסיה) מ l עד m-1 (החצי השמאלי של המערך).
  • אחרת נבדוק אם m<x, אם כן - נקרא לעצמנו מ m+1 עד r (החצי הימיני של המערך).
  • אחרת (m=x) נחזיר את m.

 

הקוד של האלגוריתם ב פסאודו קוד

(ה ~ נועד לסמן עיגול כלפי מטה)

BINARY-SEARCH (A, l, r, x)
if (r > l)
    return "not found"
m <- ~(l+r)/2~
if (A[m] > x)
    return BINARY-SEARCH (A, l, m - 1, x)
else if (A[m] < x)
    return BINARY-SEARCH (A, m + 1, r, x)
else return m
BFS Algorithm

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

 

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

בתחילת האלג’ אנו רואים את תנאי היציאה, r < l (אלו איברים שמחזיקים מצביע למערך, וז”א שהמצביע הימני, r, קטן מהמצביע השמאלי, l, ואז בעצם עברנו על כל המערך ולכן נחזיר “not found”. לאחר מכן אנו מגדירים את המשתנה m שהינו מצביע לאיבר האמצעי של המערך, ואנו בודקים אם הערך שבתוך המיקום אליו m מצביע גדול או קטן מ x (משתנה המכיל את הערך אותו אנו מחפשים), ובתאם לכך הולכים שמאלה (אם גדול) או ימינה (אם קטן) כדי להמשיך לחפש אותו בחצי המערך הנותר. אם הוא לא קטן ולא גדול, אז הוא שווה, ולכן ב else האחרון נחזיר את m.

מכיוון שהמערך ממוין אנו יודעים בוודאות שאם הערך ב [A[m גדול מ x כל האיברים שאחרי m גם גדולים ממנו ולכן אנו יכולים “לזרוק” חצי מהמערך בלי לעבור עליו.

 

הרצה של הקוד לשם המחשה של השלבים המתבצעים:

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

    1. נקבל מערך: { 30, 10, 9, 6, 5, 4, 3, 1 }. A זהו מצביע למערך, p זה מצביע לתחילת המערך (תא מס’ 0), r מצביע לסוף המערך (תא מס’ 7), ו x זהו הערך שאנחנו מחפשים, בואו ניקח לדוגמה את 10.
    2. שורה 2: אם r < p אז.., מכיוון ש r=7 ו p=0, התנאי לא מתקיים ולא ניכנס אליו.
    3. שורה 4: m יהיה שווה ל 2/(0+7) שזה (תא מס’) 3 (עיגלנו כלפי מטה).
    4. שורה 5: אם [A[m (שהוא שווה לערך 5), גדול מ x (שהוא 10) אז.., התנאי לא מתקיים.
    5. שורה 7: אחרת, אם [A[m (עדיין 5) קטן מ x (שווה ל-10) אז:
      • שורה 8: נקרא לעצמנו, כש p ישתנה ויהיה שווה ל m+1 (שזה תא מס’ 4).
      • התת מערך שאנו בודקים כרגע נראה כך: { 30, 10, 9, 6, 5 }.
      • שורה 2: אם r < p אז.., מכיוון ש r=8 ו p=4, התנאי לא מתקיים ולא ניכנס אליו.
      • שורה 4: m יהיה שווה ל 2/(4+8) שזה (תא מס’) 6 (עיגלנו כלפי מטה).
      • שורה 5: אם [A[m (הערך בתא מס’ 6, שזה 10), גדול מ x (שהוא 10) אז.., התנאי לא מתקיים.
      • שורה 7: אחרת, אם [A[m (עדיין 10) קטן מ x (שווה ל10) אז.., התנאי לא מתקיים.
      • שורה 9: אחרת, נחזיר m (שזה הערך בתא מס’ 6, והוא 10 שזה ערך אותו אנו מחפשים).

סיבוכיות זמן ריצה: ((O(lg(n.
סיבוכיות מקום: (O(1.