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، أو أكمل الدالة المعروضة.
اضغط تشغيل للمعالجة والتشغيل، ثم تحقق من الإجابة.
كودك يُعالج ويُشغل على الخادم، لذا حتى التشغيل الأول سريع.

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) لمصفوفة مرتبة. استخدم حدود 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 · ⁨تغذية راجعة ومساعدة⁩