Let's learn C

חיפוש בינארי

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

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

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

נניח שיש לנו את המערך הבא:

ואנו רוצים לדעת באיזה אינדקס נמצא האיבר 8 (אם בכלל הוא נמצא).

משתנה start מתחיל מ 0.
משתנה end מתחיל מהאיבר האחרון של המערך (גודל המערך הוא 9. לכן end שווה ל-8).
middle = (start+end)/2 ולכן יהיה שווה ל4 (כי אנחנו מדברים על מספרים שלמים).
כעת נבדוק האם בתא middle (תא 4) נמצא הערך 8.

גילינו שהערך בתא middle הוא 5 ולכן אנו מבינים שכל צד שמאל במערך שלנו קטן מ-8 ואין לנו צורך לבדוק יותר בצד זה.
בשל כך, בבדיקה הבאה שלנו נקדם את start להיות שווה לאינדקס של (middle+1).

גילינו שהערך בתא middle הוא 7 ולכן אנו מבינים שכל צד שמאל במערך שלנו קטן מ-8 ואין לנו צורך לבדוק יותר בצד זה.
בשל כך, בבדיקה הבאה שלנו נקדם את start להיות שווה לאינדקס של (middle+1).

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

דוגמה לפונקצית חיפוש בינארי:

CODE 1:


#include <stdio.h>
int binary_search(int *arr , int sizeOfArr, int key)
{
  int start = 0 , middle , end = sizeOfArr-1;
  while(start<end)
  {
    middle = (start+end) / 2;
    if(arr[middle] == key)
    {
      return middle;
    }
    else if(arr[middle] < key)
    {
      start = middle + 1;
    }
    else   
    {  
      end = middle - 1;  
    }
  }
 return -1; 
}

הסבר על הקוד:

ראשית, נצהיר על משתנים start = 0 , middle , end = sizeOfArr-1.
start ייצג לנו את תחילת המערך, middle ייצג לנו את אמצע המערך וend ייצג לנו את סוף המערך.
נרוץ על לולאת while כל עוד start קטן מend (כלומר, כל עוד אנו נמצאים במצב תקין).
בתוך הלולאה אנו תמיד נתחיל על ידי הכנסת ערך לmiddle שיהיה שווה ל:
(start+end)/2
לאחר מכן, נבדוק:

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

במידה וכן - נחזיר את האינדקס של האיבר במערך והקוד שלנו הסתיים.
במידה ולא - נמשיך בבדיקות:

האם האיבר שנמצא במערך באינדקס middle קטן מהערך שאותו אנו מחפשים?

במידה וכן - אין צורך להסתכל על הצד השמאלי (הנוכחי) של המערך משום שכל האיברים שם קטנים מהאיבר האמצעי שלנו ואנו נגיד שמעכשיו האיבר הראשון שעליו אנו מסתכלים ימצא בmiddle + 1. (הסיבה לכך שאנו נוסיף 1 היא בגלל שאין לנו צורך להסתכל יותר על איבר האמצע מהסיבוב הנוכחי בלולאה כי הוא כבר נבדק).
במידה ולא?
נתקדם לשאלות הבאות בתוך הלולאה:

האם האיבר במערך גדול מהאיבר שאותו אנו מחפשים?

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

המשך האלגוריתם:

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

חשוב לציין:

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