Searching: linear and binary · ⁨חיפוש: ליניארי ובין-מונדי⁩

English

Finding a value

A common job is to search: is a value in an array, and where?
The usual answer is the index where we found it, or -1 if it is not there.
We learn two ways: linear search (works on any array) and binary search (needs a sorted array, but is much faster).

עברית

מציאת ערך

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

English

Linear search

Look at each item from index 0 to the end.
If the item equals the target, return its index right away.
If the loop finishes with no match, return -1.

עברית

חיפוש ליניארי

סוקר כל פריט מהמדד 0 ועד הסוף.
אם הפריט שווה למטרה, חזר את המדד שלו מיידית.
אם הלופס הסתיים ללא התאמה, חזור -1.

public class Main {
    public static void main(String[] args) {
        int[] a = {4, 8, 15, 16, 23};
        int target = 15;
        int found = -1;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                found = i;
                break;       // stop early, we have it
            }
        }
        System.out.println(found);   // 2
    }
}

English

How fast is linear search?

In the worst case (the value is last, or missing) it checks every item.
For a list of n items that is up to n checks. We call this linear time.
For small arrays this is totally fine. For huge sorted arrays we can do better.

עברית

כמה מהיר חיפוש ליניארי?

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

English

Binary search needs a sorted array

Binary search only works when the array is already sorted (small to large).
It checks the middle item, then throws away half the array each step.
That is much faster: a million items take about 20 checks, not a million.

עברית

חיפוש בינארי דורש מערך מסודר

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

English

The binary search idea

Keep two bounds: low (start) and high (end).
Look at the middle index mid = (low + high) / 2.
If a[mid] equals the target, return mid.
If a[mid] is too small, the target must be on the right, so set low = mid + 1.
If a[mid] is too big, the target must be on the left, so set high = mid - 1.
Stop when low passes high; then the value is not there, return -1.

עברית

רעיון חיפוש בינארי

שמור שני גבולות: low (התחלה) ו-high (סוף).
תבדוק את המדד האמצעי mid = (low + high) / 2.
אם a[mid] שווה למטרה, חזור mid.
אם a[mid] שווה למטרה, החזר low = mid + 1.
אם a[mid] קטן מדי, המטרה חייבת להיות בימין, אז הגדר מחדש את high = mid - 1.
עצור כאשר low עובר את high; אז הערך אינו קיים, חזור -1.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12, 16, 23, 38};   // sorted!
        int target = 16;

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;     // go right
            } else {
                high = mid - 1;    // go left
            }
        }
        System.out.println(found);   // 4
    }
}

English

When a value is missing

Both searches return -1 when the target is not in the array.
For binary search, the loop ends when low > high — the bounds have crossed, so there is nowhere left to look.
Always handle the -1 case in code that calls a search.

עברית

כאשר ערך חסר

שתי החיפושים מחזירות -1 כאשר המטרה אינה נמצאת במערך.
בחיפוש בינארי, הלולאה מסתיימת כאשר low > high — הגבולות חצו זה את זה, ולכן אין מקום נוסף לחפש.
שתי שיטות החיפוש מחזירות -1 כאשר המטרה אינה במערך.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12};   // sorted
        int target = 7;            // not in the array

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        System.out.println(found);   // -1
    }
}

English

Common mistakes

Binary search needs a sorted array.
Linear search is O(n); binary is O(log n).

עברית

טעויות נפוצות

חיפוש בינארי דורש מערך מסודר.
חיפוש ליניארי הוא O(n); בינארי הוא O(log n).

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

עברית

כעת תנסו בעצמכם

כל משימה ממלאת מראש את שלד המחלקה — כתוב את הקוד שלך בתוך main, או השלם את השיטה המוצגת.
לחץ על Run כדי להרכיב ולהריץ, ולאחר מכן לחץ על Check answer.
הקוד שלך נרכב ונרץ על השרת, ולכן גם ההפעלה הראשונה היא מהירה.

Explore · ⁨חקור⁩

Linear vs binary search · ⁨חיפוש ליניארי לעומת חיפוש בינארי⁩

Binary search halves the range each step — far fewer checks. · ⁨חיפוש בין-מונדי חותך את הטווח למחצה בכל צעד — מספר בדיקות מעט יותר פחות.⁩

Complete linearSearch(int[] a, int target). Return the index of the first item equal to target, or -1 if it is not in the array. Check items from index 0 upward. · ⁨השלם linearSearch(int[] a, int target). החזר את המדד של הפריט הראשון השווה לtarget, או -1 אם הוא אינו קיים במטריצה. בדוק פריטים החל מהמדד 0 ומעלה.⁩

public class SearchUtil {
    // Return the index of target, or -1 if not found.
    public static int linearSearch(int[] a, int target) {
        return -1;   // change this
    }
}

Click Run to see the output here. · ⁨לחץ על הרץ כדי לראות את התוצא כאן.⁩

Complete binarySearch(int[] a, int target) for a sorted array. Use low/high bounds and check the middle each step. Return the index of target, or -1 if it is missing. · ⁨השלם binarySearch(int[] a, int target) עבור מטריצה מוorderedת. השתמש בגבולות low/high ובדוק את האמצע בכל צעד. החזר את מדד הtarget, או -1 אם הוא חסר.⁩

public class SearchUtil {
    // Binary search on a sorted array. Return index or -1.
    public static int binarySearch(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        // your loop here
        return -1;
    }
}

Click Run to see the output here. · ⁨לחץ על הרץ כדי לראות את התוצא כאן.⁩

Complete countOccurrences(int[] a, int target) that returns how many times target appears in a (a linear scan). Return 0 if it never appears. · ⁨השלם countOccurrences(int[] a, int target) שמחזיר כמה פעמים הtarget מופיע בa (סריקה ליניארית). החזר 0 אם לעולם לא מופיע.⁩

public class SearchUtil {
    // Count how many times target appears in a.
    public static int countOccurrences(int[] a, int target) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨לחץ על הרץ כדי לראות את התוצא כאן.⁩

Searching: linear and binary · ⁨חיפוש: ליניארי ובין-מונדי⁩

Finding a value

מציאת ערך

Linear search

חיפוש ליניארי

How fast is linear search?

כמה מהיר חיפוש ליניארי?

Binary search needs a sorted array

חיפוש בינארי דורש מערך מסודר

The binary search idea

רעיון חיפוש בינארי

When a value is missing

כאשר ערך חסר

Common mistakes

טעויות נפוצות

Now you try

כעת תנסו בעצמכם

Linear vs binary search · ⁨חיפוש ליניארי לעומת חיפוש בינארי⁩

Handout · ⁨חומר עזר⁩

Log in or create account · ⁨היכנס או צור חשבון⁩

Your subject · ⁨הנושא שלך⁩

All sections · ⁨כל הסעיפים⁩

Feedback & help · ⁨משוב וסיוע⁩