البحث الثنائي

مفهوم البحث الثنائي

يُعَدُّ البحث الثنائي (Binary Search) إحدى خوارزميات البحث الأكثر شهرةً في علم الحاسوب، إذ يتيح الوصول إلى العنصر المطلوب بسرعة عالية بفضل تعقّده الزمني Ο(log n).^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد} لا يمكن تطبيق هذه الخوارزمية إلا إذا كان ترتيب البيانات مُسبقًا؛ فوجود تسلسل تصاعدي أو تنازلي يضمن صحة عملية التقسيم المتكرر.^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد} تستند طريقة عملها إلى مبدأ «فرق تسد» (divide and conquer) الذي يُقسم المجال إلى نصفين متتاليين، ثم يُستبعد النصف الذي لا يحتوي على العنصر المستهدف، ويتكرر ذلك حتى يُعثر على القيمة أو يُستنفد المجال.^{22البحث الثنائي Binary Search - Kholood Tech Noteskholoodtechnotes.netاذهب إلى المرجع ↓يُفتح في تبويب جديد33تعلم خوارزمية البحث الثنائي في بايثون خطوة بخطوة للمبتدئينcodex-academy.orgاذهب إلى المرجع ↓يُفتح في تبويب جديد}

تتضمن خطوات البحث الثنائي ما يلي:

• تحديد العنصر الأوسط في المصفوفة المقسمة ومقارنته بالهدف؛ إذا كانا متطابقين تُنتهي العملية.^{33تعلم خوارزمية البحث الثنائي في بايثون خطوة بخطوة للمبتدئينcodex-academy.orgاذهب إلى المرجع ↓يُفتح في تبويب جديد}
• إذا كان الهدف أكبر من العنصر الأوسط، يتم إهمال النصف الأول والتركيز على النصف الثاني فقط.^{33تعلم خوارزمية البحث الثنائي في بايثون خطوة بخطوة للمبتدئينcodex-academy.orgاذهب إلى المرجع ↓يُفتح في تبويب جديد}
• إذا كان الهدف أصغر من العنصر الأوسط، يُستبعد النصف الثاني ويُستمر في النصف الأول.^{33تعلم خوارزمية البحث الثنائي في بايثون خطوة بخطوة للمبتدئينcodex-academy.orgاذهب إلى المرجع ↓يُفتح في تبويب جديد}
• تُعاد العملية على النصف المختار حتى يُعثر على العنصر أو يصبح النطاق فارغًا، ما يدل على عدم وجوده في البيانات.^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

بهذا الأسلوب، يحقق البحث الثنائي كفاءةً ملحوظةً مقارنةً بطرق البحث البسيطة مثل البحث الخطي، حيث يقلل عدد المقارنات المطلوبة بصورة جوهرية.^{22البحث الثنائي Binary Search - Kholood Tech Noteskholoodtechnotes.netاذهب إلى المرجع ↓يُفتح في تبويب جديد}

البحث الخطي

يُستَخدم البحث الثنائي (Binary Search) عندما تكون عناصر المصفوفة مرتبة ترتيبًا تصاعديًا لتسريع عملية العثور على قيمة معينة مقارنةً بالبحث الخطي.^{44البحث الثنائي - موسوعة حسوبwiki.hsoub.comاذهب إلى المرجع ↓يُفتح في تبويب جديد} يختلف هذا الأسلوب عن البحث الخطي الذي يفتتح فحص كل عنصر على حدة ولا يتطلب ترتيبًا مسبقًا للبيانات.^{55الفرق بين البحث الخطي والثنائيae.linkedin.comاذهب إلى المرجع ↓يُفتح في تبويب جديد} في البحث الثنائي يتم تقليل نطاق البحث تدريجيًا دون الحاجة إلى استنفاد جميع العناصر، ما يسمح بالوصول إلى الهدف بعد عدد أقل من الفحوصات.^{66البحث الخطي والبحث الثنائيae.linkedin.comاذهب إلى المرجع ↓يُفتح في تبويب جديد} وبالتالي، يصبح البحث الثنائي خيارًا مفضلًا للبيانات الكبيرة المرتبة، حيث يحد من عدد المقارنات المطلوبة.

من أهم خصائص البحث الثنائي:

• يتطلب أن تكون المصفوفة مرتبة مسبقًا لتطبيقه بفعالية.^{44البحث الثنائي - موسوعة حسوبwiki.hsoub.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
• يقلل نطاق البحث في كل خطوة، مما يجنب المرور على كل العناصر.^{66البحث الخطي والبحث الثنائيae.linkedin.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
• يُعَدّ أسرع من البحث الخطي في الحالات التي تكون فيها المصفوفة مرتبة وتحتوي على عدد كبير من العناصر.^{44البحث الثنائي - موسوعة حسوبwiki.hsoub.comاذهب إلى المرجع ↓يُفتح في تبويب جديد55الفرق بين البحث الخطي والثنائيae.linkedin.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

مثال توضيحي للبحث الثنائي بلغة Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

فكرة البحث الثنائي

تُعَدُّ خوارزمية البحث الثنائي (Binary Search) طريقةً تُستَخدم لتحديد موقع عنصرٍ ما داخل قائمةٍ مرتبة عبر تقليل نطاق البحث إلى نصفين بصورة متكررة، ما يجعلها أكثر كفاءةً من الفحص المتسلسل خاصةً مع القوائم الكبيرة.^{77خوارزمية البحث الثنائيae.linkedin.comاذهب إلى المرجع ↓يُفتح في تبويب جديد} تُطبَّق الخوارزمية على القوائم المرتبة تصاعديًا أو تنازليًا، وتستند إلى مبدأ تقليص عدد العناصر إلى النصف في كل خطوة، مما يحقق زمنًا لوغاريتميًا يقترب من O(log N).^{22البحث الثنائي Binary Search - Kholood Tech Noteskholoodtechnotes.netاذهب إلى المرجع ↓يُفتح في تبويب جديد}

تتمثل آلية عمل البحث الثنائي في الخطوات التالية:

• مقارنة القيمة المستهدفة بالعنصر الواقع في وسط المصفوفة المرتبة؛ إذا تطابقت تُسترجع موضع العنصر مباشرةً.^{88Binary Search - LeetCodeleetcode.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
• إذا كانت القيمة أصغر من العنصر الأوسط، يُستمر بالبحث في النصف الأدنى من المصفوفة.^{88Binary Search - LeetCodeleetcode.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
• إذا كانت القيمة أكبر، يُستمر بالبحث في النصف الأعلى من المصفوفة.^{88Binary Search - LeetCodeleetcode.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
• تُعاد العملية حتى يتم العثور على العنصر أو يصبح نطاق البحث فارغًا، ما يعني عدم وجود العنصر في القائمة.^{88Binary Search - LeetCodeleetcode.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

مثال توضيحي بلغة Python يُظهر تنفيذ الخوارزمية:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

الخطوات بمثال

تعتمد خوارزمية البحث الثنائي (Binary Search Algorithm) في عملها على مصفوفة مرتبة تصاعديًا (Ascending Sorted Array)، حيث تتتبع النطاق المستهدف باستخدام مؤشرات تسمى الحد الأدنى (Low)، والحد الأعلى (High)، والمؤشر الأوسط (Mid).^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد99خوارزمية البحث الثنائي: الشرح الأبسط والأشمل (أمثلة برمجية) - خليةkhalieah.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

لتوضيح آلية العمل، يمكن تناول مثال لعملية البحث عن العدد 23 في مصفوفة مكونة من 10 عناصر مرتبة تصاعديًا، وتكتمل العملية خلال ثلاث خطوات متتالية:^{99خوارزمية البحث الثنائي: الشرح الأبسط والأشمل (أمثلة برمجية) - خليةkhalieah.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

1. تحريك مؤشرات النطاق Low وMid وHigh تدريجيًا عبر الخطوات الثلاث لتضييق نطاق البحث.^{99خوارزمية البحث الثنائي: الشرح الأبسط والأشمل (أمثلة برمجية) - خليةkhalieah.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
2. الوصول إلى الخطوة الثالثة التي تصبح فيها قيمة Low تساوي 5 وقيمة High تساوي 6، فيُحسب المؤشر Mid عبر المعادلة Mid = 5 + (6 – 5) / 2 ليكون الناتج هو الفهرس (Index) رقم 5.^{99خوارزمية البحث الثنائي: الشرح الأبسط والأشمل (أمثلة برمجية) - خليةkhalieah.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
3. مقارنة العنصر الموجود في الفهرس 5 بالعدد المطلوب 23، وعند ثبوت تساويهما ينتهي البحث بالعثور على العنصر في الفهرس 5.^{99خوارزمية البحث الثنائي: الشرح الأبسط والأشمل (أمثلة برمجية) - خليةkhalieah.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

تتضح القوة اللوغاريتمية (Logarithmic Power) للخوارزمية في إنجاز البحث في 3 خطوات ضمن 10 عناصر، وفي نحو 30 خطوة فقط إذا احتوت المصفوفة على مليار عنصر.^{99خوارزمية البحث الثنائي: الشرح الأبسط والأشمل (أمثلة برمجية) - خليةkhalieah.comاذهب إلى المرجع ↓يُفتح في تبويب جديد} كما تتبع الخوارزمية الأسلوب نفسه للبحث عن عناصر أخرى مثل القيمة 31 في المصفوفات المرتبة.^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

التعقيد

تُعَدُّ خوارزمية البحث الثنائي (Binary Search) من أساليب البحث السريعة التي تعتمد على مبدأ «قسم تسد» (divide and‑conquer) لتقليل عدد المقارنات في كل خطوة، ولا يمكن تطبيقها إلا على مجموعة بيانات مُرتَّبة مسبقًا.^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد} تُظهر التحليلات أن التعقيد الزمني لهذه الخوارزمية يقترب من ‎O(log n)‎، إذ تُقسم المصفوفة إلى نصفين بصورة متكررة حتى يصل حجم الجزء المتبقي إلى عنصر واحد فقط، وهو ما يحدث في أسوأ الحالات بعد ما يقارب ‎log n‎ عملية تقسيم.^{44البحث الثنائي - موسوعة حسوبwiki.hsoub.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

في سياق التحليل الأسيمبتوتي (Asymptotic Analysis) يُنظر إلى عدة أبعاد لتقييم أداء البحث الثنائي، منها التعقيد المكاني (Space complexity) بالإضافة إلى حالات الأداء المختلفة مثل الحالة المثلى (Best case)، الحالة المتوسطة (Average case) والحالة الأسوأ (Worst case).^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

1. التعقيد المكاني – يعبّر عن كمية الذاكرة الإضافية المطلوبة أثناء تنفيذ الخوارزمية.^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
2. أفضل حالة – تمثل السيناريو الذي يُعثر فيه على العنصر المطلوب بأقل عدد من المقارنات.^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
3. الحالة المتوسطة – تُقَدِّر متوسط عدد المقارنات عبر جميع المدخلات الممكنة.^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
4. أسوأ حالة – تتطلب أقصى عدد من المقارنات، وهو ما يحدده تقسيم المصفوفة إلى نصفين حتى يصبح طول الجزء الواحد.^{44البحث الثنائي - موسوعة حسوبwiki.hsoub.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

إليك مثالًا مختصرًا يوضح تنفيذ البحث الثنائي على مصفوفة مرتبة بلغة Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

شروط الاستخدام

تعتمد خوارزمية البحث الثنائي (Binary Search) على أسلوب "قسّم وتغلب" (Divide and Conquer)، حيث تُنفّذ عملية البحث عبر تقسيم القائمة دائمًا إلى نصفين.^{77خوارزمية البحث الثنائيae.linkedin.comاذهب إلى المرجع ↓يُفتح في تبويب جديد} وتتميز الخوارزمية بكفاءتها العالية، إذ تساهم في تقليل وقت البحث بشكل كبير مقارنة بأسلوب البحث الخطي (Linear Search).^{77خوارزمية البحث الثنائيae.linkedin.comاذهب إلى المرجع ↓يُفتح في تبويب جديد} ولإمكانية تطبيق الخوارزمية على بنية معطيات (Data Structure)، يلزم استيفاء شروط محددة.^{1010Binary Search - GeeksforGeeksgeeksforgeeks.orgاذهب إلى المرجع ↓يُفتح في تبويب جديد}

تتضمن شروط استخدام خوارزمية البحث الثنائي ما يلي:

1. أن تكون البيانات أو القائمة المُستخدمة مفروزة ومرتبة؛ إذ إن الخوارزمية لا تعمل إلا على القوائم المرتبة.^{1115- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search | Schwarz tiger's Weblogschwarztiger.wordpress.comاذهب إلى المرجع ↓يُفتح في تبويب جديد77خوارزمية البحث الثنائيae.linkedin.comاذهب إلى المرجع ↓يُفتح في تبويب جديد1010Binary Search - GeeksforGeeksgeeksforgeeks.orgاذهب إلى المرجع ↓يُفتح في تبويب جديد}
2. أن يستغرق الوصول إلى أي عنصر من عناصر بنية المعطيات وقتًا ثابتًا (Constant Time).^{1010Binary Search - GeeksforGeeksgeeksforgeeks.orgاذهب إلى المرجع ↓يُفتح في تبويب جديد}

تطبيقات البحث الثنائي

تتعدد تطبيقات خوارزمية البحث الثنائي (Binary Search) في الأنظمة والبرمجيات نظرًا لكفاءتها الفائقة في التعامل مع البيانات الضخمة تقليلًا للوقت والجهد، حيث تعتمد على تقليص مجال البحث للنصف بشكل متكرر وتحديد موقع العنصر المطلوب بسرعة.^{77خوارزمية البحث الثنائيae.linkedin.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

وتشمل أبرز مجالات استخدام هذه الخوارزمية ما يلي:

• منصات التواصل الاجتماعي: تُستعمل الخوارزمية للعثور السريع على الأصدقاء والمستخدمين ضمن قوائم مُرتّبة تضم الأسماء أو المعرّفات، مما يرفع من جودة وكفاءة وظائف البحث.^{77خوارزمية البحث الثنائيae.linkedin.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
• القواميس والتطبيقات المعجمية: تُطبّق الخوارزمية في القواميس للوصول إلى القيم المرغوبة عبر المفتاح (Key) بدلًا من الموضع أو الفهرس (Index) المُتبع في القوائم.^{1111تنفيذ خوارزميات البحث الثنائي Binary Search في ...academy.hsoub.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}
• البحث في السجلات الكبيرة: تتيح الخوارزمية الوصول إلى عنصر محدد ضمن مليون صف من خلال إجراء عشرين مقارنة فقط.^{1212Binary Search للمبتدئ: مليون عنصر في 20 خطوة | أحمد حايسlms.ahmedhaies.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

يتم تنفيذ هذه الخوارزمية برمجيًا في التطبيقات المختلفة بأساليب متعددة ولغات مثل Python وJavaScript، حيث يُمكن صياغة دالة binary_search لتنفيذ هذه الآلية:^{1212Binary Search للمبتدئ: مليون عنصر في 20 خطوة | أحمد حايسlms.ahmedhaies.comاذهب إلى المرجع ↓يُفتح في تبويب جديد}

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

أنظر أيضاً

• API
• CSS
• HTML
• SQL
• البرمجة كائنية التوجه