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

https://stackoverflow.com/questions/1583211

21-09-2019
|

سؤال

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

المحلول

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

نصائح أخرى

بيت القصيد من البحث الثنائي هو أنه بما أنه تم فرز البيانات بالفعل، يمكنك تحديد موقع المعلومات التي تريدها بسرعة.

خذ دليل الهاتف، الذي تم فرزه حسب الاسم الأخير.

كيف يمكنك العثور على شخص ما في دليل الهاتف؟تفتحه على صفحة تفترض أنها ستكون قريبة مما تريد، ثم تبدأ في تقليب الصفحات.

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

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

يقوم البحث الثنائي بإجراء مقارنة واحدة لكل عدد مضاعف من العناصر.لذا، فإن مجموعة العناصر المكونة من 1024 عنصر تتطلب حوالي 10 مقارنات، على الأكثر، للعثور على معلوماتك، أو على الأقل معرفة عدم وجودها.

إذا قمت، قبل تشغيل البحث الثنائي الفعلي، بإجراء فحص كامل للتحقق من فرز البيانات، فمن الأفضل أن تقوم فقط بإجراء فحص للمعلومات.سيتطلب التشغيل الكامل + البحث الثنائي عمليات N + log2 N، لذلك بالنسبة لـ 1024 عنصرًا، سيتطلب الأمر حوالي 1034 مقارنة، في حين أن المسح البسيط للمعلومات سيتطلب في المتوسط النصف، وهو 512.

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

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

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

بحث ثنائي يفترض أنه يتم فرز بيانات الإدخال. إذن أنت على صواب.

الآن في التحقق بشكل عام ما إذا تم فرز البيانات بعض الوقت. لذا فإن تنفيذ هذا قبل كل بحث سيجعل البحث غير فعال حقًا.

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

المزيد من التفاصيل.