הערה: שימוש ב-sizeof על מערך מחזיר את מספר הבתים במערך:

#define N 10
#define K 20
int main() {
    int int_arr[N];
    char char_arr[K];
    printf("int_arr size = %d, char_arr size = %d\n", sizeof(int_arr), sizeof(char_arr));
}

סיכום

נסכם את ההבדלים בין מערכים סטאטיים למצביעים:

1. הצהרה על מערך סטאטי, למשל int arr[5], מקצה עבורו זכרון ישירות. לעומת זאת, הצהרה על מצביע int* arr שלא מצביע לכלום לא מקצה זכרון עבורו.
2. מידע על גודל הזכרון - שימוש ב-sizeof על מערך סטאטי תחזיר את גודל כל הזכרון שכל האיברים במערך תופסים, לעומת על מצביע שתחזיר את הגודל שהמצביע לוקח.
3. לא ניתן לשנות לאן מערך “מצביע” - למשל כאן נקבל שגיאת קומפילציה:

int arr1[4];
int arr2[3];
arr1 = arr2; // Compilation error!

הערות:

1. נשים לב שמערכים נשלחים לפונקציה כמצביע, ולכן בהכרח עוברים by reference! אין דרך להעביר מערך by value לפונקציה.
2. נשים לב שכשאנחנו מעבירים מצביע שמייצג מערך לפונקציה, אנחנו חייבים לספק ביחד איתו גם את אורך המערך - הפונקציה מקבלת מצביע בלבד, ללא מידע על כמה איברים יש בו.

חיפוש מספר במערך

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

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

#define NOT_IN_ARRAY -1
int search_in_array(int* arr, int len, int target) {
    for(int i = 0; i < len; i++) {
        if(arr[i] == target) {
            return i;
        }
    }
    return NOT_IN_ARRAY;
}

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

בעיה: בהנתן מערך באורך n, האם ניתן למצוא את האינדקס של מספר target, אם קיים, בפחות מ-n השוואות במקרה הגרוע ביותר?

זוהי לא שאלה קלה, אבל ניתן להוכיח שהתשובה היא לא בצורה מדויקת:

1. נניח בשלילה שקיים אלגוריתם שמוצא את האינדקס של target, אם קיים, ב-k < n השוואות.
2. מכיוון שיש n איברים וביצענו k השוואות, נותרו n - k איברים אליהם לא ביצענו השוואה.
3. עבור כל מערך בו target הוא אחד מה-n - k איברים הללו, האלגוריתם שלנו נכשל.

כלומר - הוכחנו בצורה מדויקת שהאלגוריתם בו מבצעים איטרציה על כל המערך הוא היעיל ביותר. האם נוכל למצוא בעיה קרובה לבעיה הזו בה יש אלגוריתם יעיל יותר?

חיפוש מספר במערך ממוין

מסתבר שיש בעיה קרובה לבעיה הקודמת - חיפוש מספר במערך ממוין.

הגדרה: מערך ממוין של שלמים באורך n הוא מערך בו לכל i < j בין 0 ל-n מתקיים arr[i] <= arr[j]. כלומר, המערך לא יורד - כל איבר קטן/שווה מהאיבר שמימינו במערך.

נגדיר את הבעיה מחדש:

בעיה: בהנתן מערך ממוין arr באורך n ומספר target, האם ניתן למצוא את האינדקס של target, אם קיים, בפחות מ-n השוואות?

מתברר שניתן לנצל את התכונה הזו בשביל לחתוך בצורה משמעותית. נבחן דוגמא:

נניח שאנחנו מחפשים את את המספר 2 במערך, שנמצא באינדקס 3. במקום להתחיל מתחילת המערך, נתחיל מהאמצע. האמצע בין 0 ל-10 הוא 5 - arr[5] = 6. זהו לא המספר שאנחנו מחפשים, אבל כאן ניתן להשתמש בצורה חכמה בעובדה שהמערך ממוין! המספר שמצאנו גדול מהמספר שאנחנו מחפשים, ולכן אם המספר שאנחנו מחפשים קיים, מובטח שהוא נמצא אך ורק לשמאלו של המספר שמצאנו. מימין ל-6 מובטח ששאר המספרים גדולים מ-6, ולכן גם בהכרח גדולים מ-2. כלומר, תחום החיפוש החוקי שלנו הוא עכשיו האיברים המסומנים:

צמצמנו בחצי את מספר האיברים שיש לחפש בהם! נחצה את האיברים הירוקים שוב באמצע ונשווה לאמצעי. כעת האמצע בין 0 ל-5 (עם עיגול כלפי מטה) הוא 2, כאשר arr[2] = 1. שוב לא מצאנו את המספר שחיפשנו, אבל מובטח לנו שהוא מימין ל-arr[2], אם הוא קיים! נחפש מימין לו בלבד כעת, ולא נשכח שצמצמנו את האיברים האחרים:

כעת נותרו שני איברים בלבד. האמצע בין 3 ו-4 (עם עיגול כלפי מטה) הוא 3 = 2 / (4 + 3), כאשר arr[3] = 2 - מצאנו את האיבר הרצוי ב-3 השוואות בלבד!

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

1. התחל את החיפוש בכל המערך - הגדר גבול שמאלי left = 0 וגבול ימני right = n - 1, ובצע איטרציות כל עוד low < high.
2. חשב את אמצע המערך, mid = (low + high) / 2.
3. אם המספר באמצע קטן מ-target, המשך את החיפוש מימין - קבע את low = mid + 1.
4. אם המספר באמצע גדול מ-target, המשך את החיפוש משמאל - קבע את high = mid - 1.
5. אחרת, המספר באמצע שווה ל-target - החזר אותו.
6. אם יצאנו מהלולאה, סימן שלא מצאנו את המספר במערך.

נכתוב מימוש:

#define NOT_FOUND -1
int binary_search(int* arr, int n, int target) {
    int low = 0;
    int high = n - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(target > arr[mid]) {
            low = mid + 1;
        } else if(target < arr[mid]) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return NOT_FOUND;
}

הערה: בהרבה קורסים וספרים קוראים לאלגוריתם זה “אריה במדבר”.

חיפוש בינארי - ניתוח מתמטי

כעת נבצע ניתוח מתמטי של כמות הפעולות הנדרשות לביצוע חיפוש בינארי. בהמשך כשנלמד על סיבוכיות נבין יותר את החשיבות של ניתוח זה. כעת, ננתח שאלה פשוטה - כמה פעולות יש לבצע בחיפוש בינארי של מערך באורך n?

נניח לפשטות ש-n הוא חזקה של 2, כלומר k שלם כך ש-n = 2^k. בכל איטרציה במהלך החיפוש הבינארי, גודל תת-המערך בו אנחנו מחפשים נחתך בחצי, עד שגודלו 1 בעת ההשוואה האחרונה. כלומר, גודל המערך בכל איטרציה יהיה:

1. n
2. n / 2
3. n / 4 … עד לאיטרציה ה-t בה גודל תת-המערך הוא n / 2^t. כמה איטרציות יקח להגיע ל-1?

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

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

תרגילים

תרגיל 1

נתון מערך ממוין של int באורך n > 0 ומספר מטרה target. כתבו פונקציה המחזירה את המספר הקרוב ביותר ל-target במערך.

פתרון

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

int abs(int a) {
    return a >= 0 ? a : -a;
}
int find_closest(int* arr, int n, int target) {
    int min_distance = MAX_INT;
    int closest = arr[0];
    for(int i = 0; i < n; i++) {
        int curr_distance = abs(target - arr[i]);
        if(curr_distance < min_distance) {
            min_distance = curr_distance;
            closest = arr[i];
        }
    }
    return closest;
}

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

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

למקרים 1 ו-2 מספיקים בדיקות לאיבר הראשון והאחרון של המערך - מכיוון שהמערך ממוין מספיק להשוות אליהם. למקרה 3 אפשר להשתמש בחיפוש בינארי. עבור מקרה 4, יתקבל כי low ו-high יהיו חסמים תחתון ועליון בהתאמה של target, ורק צריך לבדוק איזה מהם יותר קרוב - נשתמש עבור כך בפונקציית עזר לערך מוחלט:

int abs(int a) {
    return a >= 0 ? a : -a;
}
int find_closest(int* arr, int n, int target) {
    if(target <= arr[0]) {
        return arr[0];
    }
    if(target >= arr[n - 1]) {
        return arr[n - 1];
    }
    int low = 0;
    int high = n - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(target > arr[mid]) {
            low = mid + 1;
        } else if(target < arr[mid]) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    if(abs(arr[low] - target) < abs(arr[high] - target)) {
        return arr[low];
    } else {
        return arr[high];
    }

}

תרגיל 2 - סעיף א׳

נתון מטריצה בפורמט מערך דו-מימדי של שלמים int** matrix עם מימדים int n, int m. נתון כי כל שורה במערך ממוינת. כתבו פונקציה המבצעת חיפוש בינארי במטריצה.

פתרון

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

#define NOT_FOUND -1
int bsearch(int* arr, int n);
int bsearch_matrix(int** matrix, int n, int m, int target) {
    for(int i = 0; i < n; i++) {
        int index = bsearch(matrix[i], m, target);
        if(index != NOT_FOUND) {
            return index;
        }
    }
    return NOT_FOUND;
}

תרגיל 2 - סעיף ב׳

כעת נתון כי מעבר לכך שכל שורה ממוינת, האיבר האחרון בכל שורה קטן/שווה מהאיבר הראשון בשורה אחריו. למשל:

כתבו פונקציה המבצעת חיפוש בינארי אופטימלי במטריצה.

פתרון

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

נבחן את הבעיה מחדש:

1. במטריצה יש m*n - 1 איברים. נמספר את כל האיברים במטריצה מ-0 ל-mn - 1 בהתאמה.
2. בהנתן אינדקס כלשהו i במערך ה-״מושטח״, הוא שייך לשורה ה-i / m ולעמודה ה-i % m. ניתן לחשוב על זאת כך - בהנתן i, המספר i / m הוא מספר השורות המלאות שניתן להכניס ב-i מספרים, ו-i % m הוא השארית שיש להתקדם לתוך אותה שורה לאחר מכן.
3. נבצע את החיפוש הבינארי בצורה זהה למקרה המוכר, רק שאת השליפה של האיבר מהמערך נעשה בצורה מעט זהירה יותר עם האינדקסים הנכונים.

#define NOT_FOUND -1
int bsearch_matrix(int** matrix, int n, int m, int target) {
    int low = 0, high = n * m - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        int row = mid / m;
        int col = mid % m;
        int val = matrix[row][col];
        if (val == target) {
            return mid;
        } if (val < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return NOT_FOUND;
}

תרגיל 3

בהנתן מספר שלם חיובי n, כתבו פונקציה שמחשבת את השורש שלו מעוגל לשלם הקרוב ביותר. על הפונקציה שלכם לבצע לכל היותר $c\log_2 n$ פעולות, כאשר $c$ קבוע חיובי כלשהו.

פתרון

ניתן בהתחלה לחשוב - מה הקשר בין השאלה הזו לחיפוש בינארי? הרמז נמצא בדרישה לביצוע לכל היותר $c\log_2n$ פעולות. ראינו כי חיפוש בינארי מבצע סקאלה של $\log_2n$ פעולות, ולכן יתכן שאפשר לבצע פה משהו שדומה לחיפוש בינארי. כיצד?

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

1. נתונה וריאציה על בעית החיפוש במערך הממוין - בהנתן מערך ממוין ומספר כלשהו lower_bound, יש למצוא מספר כלשהו במערך שקטן מ-lower_bound. כתבו את הפונקציה bsearch_find_lower(int* arr, int n, int lower_bound) שפותרת את הבעיה.
2. נתון מערך int* temps באורך שמדד את הטמפרטורה בכוס כל דקה לאורך n דקות. מצאו את הדקה הראשונה בה המים היו רותחים (כלומר, הטמפרטורה הייתה גדולה;שווה מ-100 מעלות).
3. מה יחזיר אלגוריתם החיפוש הבינארי במידה וקיימים מספר מקרים של target במערך נתון?
4. נתונה וריאציה על בעית החיפוש במערך ממוין - יש למצוא את האינדקס הראשון של המספר המבוקש. למשל, אם המערך הוא:

ורוצים למצוא את המספר 3, יש להחזיר את האינדקס 2 בלבד - האינדקס 3 הוא טעות. כתבו את הפונקציה bsearch_find_first(int* arr, int n) הפותרת את הבעיה.

5. נתון מערך ממוין שהזיזו אותו בצורה ציקלית ב-k איברים. למשל, עבור המערך הבא:

והזזה ציקלית של k = 2, נקבל את המערך הבא:

כתבו פונקציה המבצעת חיפוש בינארי במערך שהוזז ציקלית ב-k איברים.

6. נתון מערך ממוין של שלמים באורך n - 1. נתון כי כל השלמים בין 0 ל-n - 1 (כולל) מופיעים במערך, חוץ מאחד בודד שאינו מופיע. כתבו פונקציה שמוצאת את המספר שאינו מופיע.