خوارزمية البحث الثنائي: الوظيفة والفوائد وتعقيد الوقت والمكان

مقدمة

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

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

لا يشترط وجود خبرة في الترميز. 360 درجة الدعم الوظيفي. دبلوم PG في التعلم الآلي والذكاء الاصطناعي من IIIT-B وما فوق.

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

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

• إذا كانت القيمة المرغوبة مساوية لقيمة المؤشر المركزي ، فسيتم إرجاع الفهرس كإجابة.

• إذا كانت القيمة المستهدفة أقل من صفقة المؤشر المركزي في القائمة ، فسيتم تجاهل الجانب الأيمن من القائمة.

• إذا كانت القيمة المرغوبة أكبر من قيمة المؤشر المركزي ، فسيتم تجاهل النصف الأيسر.

• ثم يتم تكرار العملية في القوائم المختصرة حتى يتم العثور على القيمة الهدف.

مثال 1

دعونا نلقي نظرة على الخوارزمية بمثال. افترض أن هناك قائمة بالأرقام التالية:

1 ، 15 ، 23 ، 7 ، 6 ، 14 ، 8 ، 3 ، 27

لنأخذ القيمة المرغوبة على أنها 27. العدد الإجمالي للعناصر في القائمة هو 9.

الخطوة الأولى هي فرز القائمة. بعد الفرز ، ستبدو القائمة كما يلي:

1 ، 3 ، 6 ، 7 ، 8 ، 14 ، 15 ، 23 ، 27

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

نظرًا لأن 27 أكبر من 8 ، فإننا نتجاهل الجزء الأيسر ونجتاز الجانب الأيمن من القائمة فقط. القائمة الجديدة لاجتيازها هي:

14 ، 15 ، 23 ، 27

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

يمكن اعتبار الفهرس المركزي الجديد العنصر الثاني أو الثالث ، اعتمادًا على التنفيذ. هنا ، سوف نعتبر العنصر الثالث مركزيًا. تتم مقارنة القيمة 23 بالقيمة 27. نظرًا لأن القيمة أكبر من القيمة المركزية ، فسوف نتجاهل النصف الأيسر.

القائمة المراد اجتيازها هي:

27

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

المثال رقم 2

في نفس القائمة ، لنفترض أن القيمة المرغوبة هي 2.

أولاً ، تتم مقارنة القيمة المركزية ثمانية بـ 2. نظرًا لأن القيمة المطلوبة أصغر من القيمة المركزية ، فإننا نحصر تركيزنا إلى الجانب الأيسر من القائمة.

سيتألف الاجتياز الجديد من:

1 ، 3 ، 6 ، 7

لنأخذ العنصر المركزي كعنصر ثانٍ. تتم مقارنة القيمة المرغوبة 2 مع 3. نظرًا لأن القيمة لا تزال أصغر ، نقوم مرة أخرى بتضييق التركيز إلى الجانب الأيسر من القائمة.

سيتألف الاجتياز الجديد من:

1

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

شهادة متقدمة في علوم البيانات ، أكثر من 250 شريك توظيف ، أكثر من 300 ساعة من التعلم ، 0٪ EMI

تعقيد الزمان والمكان

التعقيد الزمني لخوارزمية البحث الثنائي هو O (log n). سيكون تعقيد الوقت في أفضل حالة هو O (1) عندما يتطابق المؤشر المركزي مباشرة مع القيمة المطلوبة. قد يكون السيناريو الأسوأ هو القيم الموجودة في أي من طرفي القائمة أو القيم غير الموجودة في القائمة.

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

1. الطريقة التكرارية
2. الطريقة العودية

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

في الطريقة التكرارية ، سيكون تعقيد الفضاء هو O (1). بينما في الطريقة العودية ، سيكون تعقيد الفضاء هو O (سجل ن).

فوائد

• خوارزمية البحث الثنائي هي خوارزمية بحث بسيطة إلى حد ما يتم تنفيذها.

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

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

الخروج: تصنيف شجرة القرار: كل ما تحتاج إلى معرفته

خاتمة

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

إذا كنت مهتمًا بالتعرف على علوم البيانات ، فراجع دبلوم PG في IIIT-B & upGrad في علوم البيانات والذي تم إنشاؤه للمهنيين العاملين ويقدم أكثر من 10 دراسات حالة ومشاريع ، وورش عمل عملية عملية ، وإرشاد مع خبراء الصناعة ، 1- على - 1 مع موجهين في الصناعة ، وأكثر من 400 ساعة من التعلم والمساعدة في العمل مع الشركات الكبرى.