خوارزميات البحث: متى تستخدم البحث الخطي أو الثنائي؟

أختار البحث الخطي ولا الثنائي؟

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

مثال تتبعه بنفسك

القيم المرتبة هي 3 و7 و11 و18 و25. نبحث عن 18. المنتصف 11، ولذلك نكمل في الجزء الأعلى من المجال، ثم نصل إلى 18.

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

اتفق على معنى الحدود

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

حساب المنتصف بصيغة low + (high - low) / 2 يتجنب جمع فهرسين كبيرين مباشرة، بشرط صحة المجال والحساب وأنواع القيم.

قارن الاستخدام الكامل

في المصفوفة المرتبة، عدد مقارنات البحث الثنائي O(log n)، مقابل O(n) في أسوأ حالات المرور الخطي. لا تنقل هذا الاستنتاج تلقائيًا إلى بنية لا تدعم الوصول بالفهرس بكفاءة.

ماذا تقصد مع التكرار؟

في 2 و5 و5 و5 و9، سؤال وجود 5 مختلف عن مكان أول 5 أو عدد مرات ظهورها. اكتب الناتج المطلوب قبل اختيار التنفيذ.

اختبر قيمة أصغر من الجميع وأكبر من الجميع وبين عنصرين. وراجع الفراغ والعنصر الواحد حسب اتفاق الدالة.

تمرين

تتبع البحث عن 14 في 4 و8 و14 و21 و30 و42. سجل المجال والمنتصف في كل خطوة. ثم اشرح لماذا قد لا تحتاج إلى ترتيب قائمة جديدة إذا كان المطلوب بحثًا واحدًا فقط.

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