חיפוש בינארי

חיפוש במערך בזמן O(n) הוא טוב, אך אפשר לייעל אותו עוד יותר ל־O(log n) באמצעות שיטה שנקראת חיפוש בינארי. 

תנאי לשימוש בחיפוש בינארי: יש למיין את איברי המערך בסדר עולה או בסדר יורד.

לדוגמה, 

int Arr[]={1,2,3,4,5};
int Brr[]={5,3,9,6,7};

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

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

ההיגיון הבסיסי

בדקו את האיבר שנמצא בדיוק באמצע המערך, 

1. אם הוא שווה למפתח, הדפיסו אותו,
2.  אם הוא קטן מאיבר המפתח, חפשו בחלק הימני של המערך שנותר, 
3.  אם הוא גדול יותר, חפשו בחלק השמאלי של המערך שנותר.

חזרו על התהליך עד שתמצאו את איבר המפתח הרצוי, אחרת החזירו ‎-1.

התהליך בפירוט

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

    int s=0; //התחלה
    int e=n; //סוף
    
    while(s<=e){
    
    }

2. מצאו את האיבר האמצעי באמצעות החישוב ‎(s+e)/2. אם mid שווה בדיוק למפתח, החזירו אותו.

    int s=0; //התחלה
    int e=n; //סוף
    
    while(s<=e){
    
        int mid=(s+e)/2;  //אמצע המערך

        if(arr[mid]==key){   //אם הוא שווה, החזר אותו
            return mid;
        }
    
    }

3. אם האיבר האמצעי גדול מאיבר המפתח, פירוש הדבר שאיבר המפתח חייב להימצא בחלק השמאלי של המערך. לכן, מזיזים את סוף המערך ל־mid-1. כעת יש לנו מערך בגודל n/2 בלבד, שעליו חוזרים על התהליך הזה.

    int s=0; //התחלה
    int e=n; //סוף
    
    while(s<=e){
    
        int mid=(s+e)/2;  //אמצע המערך

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;         //הזז את נקודת הסיום ל-mid-1
        }
    
    }

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

    int s=0;
    int e=n;
    while(s<=e){
        int mid=(s+e)/2;

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;
        }
        else{
            s=mid+1;   //העבר את נקודת ההתחלה ל-mid+1
        }
    }

מריצים את התוכנית עד שמוצאים את האיבר. אם האיבר אינו קיים, מחזירים ‎-1.

סיבוכיות זמן

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