فهم البحث الثنائي (Binary Search) مع أمثلة في Python، Java، و C

1. مقدمة عن المشكلة

وصف المشكلة:
البحث الثنائي هو خوارزمية فعّالة للبحث عن عنصر في قائمة مرتبة من العناصر. تعمل عن طريق تقسيم القائمة بشكل متكرر إلى نصفين حتى تصل إلى موقع العنصر المستهدف.

حالة استخدام:
تخيل أن لديك دليل هاتف مرتب حسب الأسماء، وتريد العثور على رقم هاتف شخص معين. بدلاً من البحث من خلال كل إدخال، يمكنك البدء من منتصف الدليل، واستبعاد نصف الإدخالات مع كل خطوة.

المدخلات والمخرجات:

• المدخلات: مصفوفة مرتبة من الأعداد الصحيحة arr[] وقيمة الهدف x.
• المخرجات: إرجاع فهرس x في arr إذا كان موجودًا؛ وإلا، إرجاع -1.

2. شرح تعليمي للحل

كيفية عمل البحث الثنائي:

1. التقسيم: ابدأ بالمصفوفة بالكامل.
2. المقارنة: قارن العنصر المستهدف بالعنصر الموجود في منتصف المصفوفة.
3. القرار:
   • إذا كان العنصر في المنتصف هو الهدف، أعد فهرسه.
   • إذا كان الهدف أصغر من العنصر في المنتصف، تجاهل النصف الأيمن.
   • إذا كان الهدف أكبر، تجاهل النصف الأيسر.
4. التكرار: كرر العملية على النصف المناسب حتى تجد العنصر أو يصبح النصف غير موجود.

تعقيد الوقت:

• أفضل حالة: O(1) عندما يكون العنصر في المنتصف هو الهدف.
• متوسط وأسوأ حالة: O(log n)، حيث n هو عدد العناصر في المصفوفة.

تعقيد المساحة:

• النسخة التكرارية: O(1)
• النسخة العودية: O(log n) بسبب مكدس الاستدعاء.

3. الحل في Python

def binary_search(arr, x):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # تجنب تجاوز القيم الكبيرة

        # التحقق مما إذا كان x موجودًا في المنتصف
        if arr[mid] == x:
            return mid
        # إذا كان x أكبر، تجاهل النصف الأيسر
        elif arr[mid] < x:
            left = mid + 1
        # إذا كان x أصغر، تجاهل النصف الأيمن
        else:
            right = mid - 1

    # إذا وصلنا هنا، فهذا يعني أن العنصر غير موجود
    return -1

# استخدام المثال
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
print("العنصر موجود في الفهرس" if result != -1 else "العنصر غير موجود في المصفوفة", result)

4. الحل في Java

public class BinarySearch {
    // يُرجع فهرس x إذا كان موجودًا في arr[], وإلا يُرجع -1
    int binarySearch(int arr[], int x) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;

            // تحقق مما إذا كان x موجودًا في المنتصف
            if (arr[mid] == x)
                return mid;

            // إذا كان x أكبر، تجاهل النصف الأيسر
            if (arr[mid] < x)
                left = mid + 1;

            // إذا كان x أصغر، تجاهل النصف الأيمن
            else
                right = mid - 1;
        }

        // إذا وصلنا هنا، فهذا يعني أن العنصر غير موجود
        return -1;
    }

    // طريقة القيادة لاختبار ما سبق
    public static void main(String args[]) {
        BinarySearch ob = new BinarySearch();
        int arr[] = {2, 3, 4, 10, 40};
        int x = 10;
        int result = ob.binarySearch(arr, x);
        if (result == -1)
            System.out.println("العنصر غير موجود");
        else
            System.out.println("العنصر موجود في الفهرس " + result);
    }
}

5. الحل في C

#include <stdio.h>

// دالة البحث الثنائي التكرارية. تُرجع موقع x في المصفوفة المعطاة arr[l..r] إذا كان موجودًا، وإلا تُرجع -1
int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;

        // تحقق مما إذا كان x موجودًا في المنتصف
        if (arr[mid] == x)
            return mid;

        // إذا كان x أكبر، تجاهل النصف الأيسر
        if (arr[mid] < x)
            l = mid + 1;

        // إذا كان x أصغر، تجاهل النصف الأيمن
        else
            r = mid - 1;
    }

    // إذا وصلنا هنا، فهذا يعني أن العنصر غير موجود
    return -1;
}

int main(void) {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1)
        printf("العنصر غير موجود في المصفوفة");
    else
        printf("العنصر موجود في الفهرس %d", result);
    return 0;
}