تمارين

مراجعة المفاهيم

كيف يضيّق البحث الثنائي مجال البحث

ابحث عن 16 في المصفوفة المرتبة [2, 5, 8, 12, 16, 23, 38]. استخدم المجال المغلق [i, j] واحسب نقطة المنتصف بالصيغة $m=i+(j-i)/2$ بعد التقريب للأسفل.

في كل جولة، اكتب (i, j, m) والعنصر الأوسط وكيف يُضيّق المجال بعد ذلك، حتى العثور على الهدف.

الإجابة

يسير البحث كما يلي:

الجولة	`(i, j, m)`	العنصر الأوسط	الخطوة التالية
1	`(0, 6, 3)`	12	`12 < 16`، عيّن `i = 4`
2	`(4, 6, 5)`	23	`23 > 16`، عيّن `j = 4`
3	`(4, 4, 4)`	16	عُثر على الهدف؛ أعد الفهرس 4

لأن المصفوفة مرتبة، فعندما تكون القيمة الوسطى أصغر من الهدف يمكن استبعاد العنصر الأوسط وكل ما يقع على يساره. وعندما تكون القيمة الوسطى أكبر من الهدف يمكن استبعاد العنصر الأوسط وكل ما يقع على يمينه.

الحدان الأيسر والأيمن للعناصر المكررة

ابحث عن العدد 2 في المصفوفة [1, 2, 2, 2, 4, 6]. يستخدم أحد الطلاب البحث الثنائي، ويعود فوراً بعد العثور على الهدف عند الفهرس 2، ويقول: "الفهرس 2 هو الحد الأيسر للعدد 2."

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

الإجابة

قول الطالب غير صحيح. فالعودة بمجرد العثور على أحد مواضع الرقم 2 تضمن فقط أنك وجدت موضعاً ما للرقم 2، وليس الموضع الأقصى يساراً أو يميناً. وهنا الحد الأيسر هو الفهرس 1 والحد الأيمن هو الفهرس 3.
عند البحث عن الحد الأيسر، واصل البحث في الجهة اليسرى حتى إذا كان العنصر الأوسط مساوياً للرقم 2. على سبيل المثال، مع مجال مغلق، عيّن j = m - 1.
عند البحث عن الحد الأيمن، واصل البحث في الجهة اليمنى بعد أن يكون العنصر الأوسط مساوياً للرقم 2. على سبيل المثال، عيّن i = m + 1.

اختيار طريقة البحث المناسبة لبيانات مختلفة

لكل حالة مما يلي، اختر طريقة مناسبة من بين "البحث الخطي" و"البحث الثنائي" و"جدول التجزئة"، واشرح السبب:

البحث مراراً ضمن $10^7$ عدد صحيح مرتبة مسبقاً ولا تتغير أبداً، دون بناء أي بنية بيانات إضافية.
فحص وجود مفتاح مراراً في مجموعة يكثر فيها الإدراج والحذف. ولا يلزم أن تبقى المجموعة مرتبة، ولا حاجة إلى أي بحث نطاقي.
البحث عن قيمة في مصفوفة غير مرتبة مرة واحدة فقط.

الإجابة

البحث الثنائي: البيانات مرتبة وثابتة، لذا يستغرق البحث زمن $O(\log n)$ دون مساحة إضافية.
جدول التجزئة: عندما توزّع دالة التجزئة المفاتيح بشكل متوازن إلى حد ما بين الدلاء، تستغرق عمليات الإدراج والحذف والبحث بالمفتاح زمن $O(1)$ في المتوسط.
امسح المصفوفة مباشرة من البداية إلى النهاية. فعند البحث مرة واحدة فقط، يتطلب ترتيب المصفوفة أو بناء جدول تجزئة معالجة المصفوفة كاملة أولاً، لذا لا يقلل أي منهما إجمالي العمل في هذه المهمة الواحدة.

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

تمارين برمجية

البحث الثنائي في مصفوفة مرتبة

معطى مصفوفة أعداد صحيحة nums مرتبة ترتيباً تصاعدياً صرفاً وقيمة هدف target، استخدم البحث الثنائي للعثور على target. فإن وُجد، أعد فهرسه في المصفوفة؛ وإلا، أعد -1.

تلميحات

المجال الأولي هو left = 0 وright = n - 1؛ ويظل غير فارغ ما دام left <= right
احسب نقطة المنتصف بالصيغة mid = left + (right - left) // 2
إذا كان nums[mid] أصغر من target، انقل الحد الأيسر إلى mid + 1؛ وإذا كان nums[mid] أكبر من target، انقل الحد الأيمن إلى mid - 1؛ وإذا تساويا، أعد النتيجة فوراً

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

نقطة الإدراج في مصفوفة مرتبة

معطى مصفوفة أعداد صحيحة nums مرتبة ترتيباً تصاعدياً صرفاً وقيمة هدف target.

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

تلميحات

قد تكون الإجابة 0 أو طول المصفوفة n
مع مجال مغلق، إذا كان nums[mid] أكبر من أو يساوي target، عيّن right = mid - 1 وواصل الفحص أكثر نحو اليسار؛ وإلا، عيّن left = mid + 1
عند انتهاء الحلقة، تكون left هي نقطة الإدراج

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

السابق ملخص التالي الترتيب