خوارزمية البحث الثنائية مع مثال

قبل أن نتعلم البحث الثنائي، دعونا نتعلم:

ما هو البحث؟

البحث عبارة عن أداة مساعدة تمكن مستخدمها من العثور على المستندات أو الملفات أو الوسائط أو أي نوع آخر من البيانات الموجودة داخل قاعدة البيانات. يعمل البحث على مبدأ بسيط وهو مطابقة المعايير مع السجلات وعرضها للمستخدم. بهذه الطريقة، تعمل وظيفة البحث الأساسية.

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

البحث الثنائي هو نوع متقدم من خوارزمية البحث التي تقوم بالعثور على البيانات وجلبها من قائمة عناصر مرتبة. يتضمن مبدأ العمل الأساسي الخاص بها تقسيم البيانات الموجودة في القائمة إلى النصف حتى يتم تحديد القيمة المطلوبة وعرضها للمستخدم في نتيجة البحث. يُعرف البحث الثنائي عادةً باسم أ بحث نصف فاصل أو بحث لوغاريتمي.

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

يعمل البحث الثنائي في المتابعةwing طريقة:

  • تبدأ عملية البحث عن طريق تحديد موقع العنصر الأوسط في مجموعة البيانات التي تم فرزها
  • بعد ذلك، تتم مقارنة القيمة الرئيسية بالعنصر
  • إذا كانت قيمة المفتاح أصغر من العنصر الأوسط، فإن عمليات البحث تحلل القيم العليا للعنصر الأوسط للمقارنة والمطابقة
  • في حالة كانت القيمة الرئيسية أكبر من العنصر الأوسط، تقوم عمليات البحث بتحليل القيم الأدنى إلى العنصر الأوسط للمقارنة والمطابقة

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

دعونا نلقي نظرة على مثال القاموس. إذا كنت بحاجة إلى العثور على كلمة معينة، فلن يقوم أحد بمراجعة كل كلمة بطريقة تسلسلية ولكن يحدد موقع الكلمة المطلوبة بشكل عشوائيarest الكلمات للبحث عن الكلمة المطلوبة.

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

الصورة أعلاه توضح المتابعةwing:

  1. لديك مصفوفة مكونة من 10 أرقام، ويجب العثور على العنصر 59.
  2. يتم تمييز جميع العناصر بالفهرس من 0 إلى 9. الآن، يتم حساب منتصف المصفوفة. للقيام بذلك، عليك أن تأخذ القيمتين اليسرى واليمنى للمؤشر وتقسمهما على 2. والنتيجة هي 4.5، لكننا نأخذ قيمة الأرضية. وبالتالي فإن الوسط هو 4.
  3. تقوم الخوارزمية بإسقاط كافة العناصر من الوسط (4) إلى الحد الأدنى لأن 59 أكبر من 24، والآن يبقى للمصفوفة 5 عناصر فقط.
  4. الآن، 59 أكبر من 45 وأقل من 63. الوسط هو 7. ومن ثم تصبح قيمة الفهرس الأيمن وسطًا – 1، وهو ما يساوي 6، وتظل قيمة الفهرس الأيسر كما هي من قبل، وهي 5.
  5. عند هذه النقطة، تعلم أن 59 يأتي بعد 45. وبالتالي، يصبح المؤشر الأيسر، وهو 5، في المنتصف أيضًا.
  6. تستمر هذه التكرارات حتى يتم تقليل المصفوفة إلى عنصر واحد فقط، أو يصبح العنصر الذي سيتم العثور عليه في منتصف المصفوفة.

مثال 2

دعونا نلقي نظرة على فولوwing مثال لفهم عمل البحث الثنائي

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

  1. لديك مصفوفة من القيم المصنفة تتراوح من 2 إلى 20 وتحتاج إلى تحديد موقع 18.
  2. متوسط ​​الحدين الأدنى والأعلى هو (l + r) / 2 = 4. القيمة التي يتم البحث عنها أكبر من الوسط وهو 4.
  3. يتم إسقاط قيم الصفيف الأقل من الوسط من البحث ويتم البحث عن القيم الأكبر من القيمة المتوسطة 4.
  4. هذه عملية تقسيم متكررة حتى يتم العثور على العنصر الفعلي المطلوب البحث عنه.

لماذا نحتاج إلى البحث الثنائي؟

التاليwing الأسباب التي تجعل البحث الثنائي خيارًا أفضل لاستخدامه كخوارزمية بحث:

  • يعمل البحث الثنائي بكفاءة على البيانات المصنفة بغض النظر عن حجم البيانات
  • بدلاً من إجراء البحث من خلال الاطلاع على البيانات في تسلسل، تقوم الخوارزمية الثنائية بالوصول عشوائيًا إلى البيانات للعثور على العنصر المطلوب. وهذا يجعل دورات البحث أقصر وأكثر دقة.
  • يقوم البحث الثنائي بإجراء مقارنات بين البيانات المصنفة بناءً على مبدأ الترتيب بدلاً من استخدام مقارنات المساواة، والتي تكون أبطأ وغير دقيقة في الغالب.
  • بعد كل دورة بحث، تقوم الخوارزمية بتقسيم حجم المصفوفة إلى نصفين وبالتالي في التكرار التالي ستعمل فقط في النصف المتبقي من المصفوفة

تعرف على البرنامج التعليمي التالي الخاص بنا البحث الخطي: مثال بايثون، C++

نبذة عامة

  • البحث عبارة عن أداة مساعدة تمكن مستخدمها من البحث عن المستندات والملفات وأنواع البيانات الأخرى. البحث الثنائي هو نوع متقدم من خوارزمية البحث التي تقوم بالعثور على البيانات وجلبها من قائمة عناصر مرتبة.
  • يُعرف البحث الثنائي عمومًا بالبحث بنصف الفاصل الزمني أو البحث اللوغاريتمي
  • إنه يعمل عن طريق تقسيم المصفوفة إلى نصفين عند العثور على كل تكرار تحت العنصر المطلوب.
  • خوارزمية ثنائية يأخذ منتصف المصفوفة عن طريق قسمة مجموع قيم الفهرس اليسرى وأقصى اليمين على 2. الآن، تقوم الخوارزمية بإسقاط الحد الأدنى أو العلوي للعناصر من منتصف المصفوفة، اعتمادًا على العنصر الذي سيتم العثور عليه.
  • تقوم الخوارزمية بالوصول بشكل عشوائي إلى البيانات للعثور على العنصر المطلوب. وهذا يجعل دورات البحث أقصر وأكثر دقة.
  • يقوم البحث الثنائي بإجراء مقارنات بين البيانات المصنفة بناءً على مبدأ الترتيب بدلاً من استخدام مقارنات المساواة البطيئة وغير الدقيقة.
  • البحث الثنائي غير مناسب للبيانات غير المصنفة.