العثور على مفقود 32 بت عدد صحيح بين فرزها مجموعة تحتوي على أكثر من 4 مليارات رجات

Question

هذا هو المشكلة هو موضح في Programming pearls.أنا لا يمكن أن نفهم الثنائية طريقة البحث descrbied من قبل المؤلف.يمكن لأي واحد يساعد على التفاصيل ؟ شكرا

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

تحرير:شكرا لكم جميعا على إجابة ممتازة و التعليقات !أهم درس أقرضته من حل هذا السؤال البحث الثنائية لا ينطبق فقط على فرز مجموعة!

Answer 1

هناك بعض مزيد من المعلومات حول هذا الموقع.ونقلت من هناك:

"ومن المفيد أن عرض هذا البحث الثنائية حيث عشرين البتات التي تمثل كل عدد صحيح.في أول تمريرة من الخوارزمية نقرأ (على الأكثر) مليون إدخال الأعداد الصحيحة وكتابة تلك مع الرائد صفر قليلا إلى شريط واحد مع رائد بت واحد إلى آخر الشريط.واحدة من تلك الأشرطة يحتوي على أكثر من 500 ، 000 الاعداد الصحيحه ، لذلك نحن بجانب استخدام هذا الشريط الحالي الإدخال و كرر عملية التحقيق ، ولكن هذه المرة على القطعة الثانية.إذا كان الأصل إدخال الشريط يحتوي على عناصر N, الأول يمر قراءة الأعداد الصحيحة N, الثانية تمر في معظم N/2 ، والثالثة تمر في معظم N/4 ، وهلم جرا ، وبالتالي فإن إجمالي وقت تشغيل يتناسب مع N.المفقودين صحيح يمكن العثور عليها عن طريق الفرز على الشريط ثم المسح الضوئي ، لكن ذلك يتطلب وقتا يتناسب مع N log N."

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

Answer 2

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

بمجرد أن يتم الانتهاء, يمكنك اختيار أي من ملفات أصغر ، ثم كرر العملية باستخدام [الأدنى, نقطة الوسط] أو (الوسط, العلوي] ك مجموعة جديدة ، حتى ملف مجموعة صغيرة بما يكفي للانتقال إلى الصورة النقطية نمط (أو واحد من ملفات الإخراج الخاص بك فارغ).

داميان

Answer 3

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

وهذا ينطبق على المشكلة الأصلية كيف تعرف أن هناك بعض أرقام مفقودة في المقام الأول أيضا.

Answer 4

إذا كنت تنظر الأرقام في النطاق من 1 إلى ن ؛ نصفهم أكبر من ن/2 و نصف من لهم أصغر من N/2

هم أكبر من N/2 يكون MSB تعيين واحد ؛ MSB = 0 أصغر.

القسم مجموعة كاملة على أساس الطيور الحوامة المهاجرة والتي سوف تعطيك مجموعتين :مجموعة من الأرقام أصغر من N/2 وتعيين عدد أكبر من N/2

القسم أصغر في الحجم وقد العنصر المفقود.

في الخطوة التالية ، استخدام القادم الطيور الحوامة المهاجرة.

1. إذا كان أصغر من مجموعة أقل من N/2 نصفهم أقل من N/4 (2 MSB=0) و النصف الآخر أكبر من N/4 (2 MSB=1)

2. إذا كان أصغر من مجموعة أكبر من N/2 نصفهم أقل من N/2+ن/4 (2 MSB=0) و النصف الآخر أكبر من N/2+ن/4 (2 MSB=1)

كل جولة سيتم تخفيض مساحة البحث و هذا الأمر.

 Sum ( N / 2^i ) for 0 <= i < log N gives you O(N)

Answer 5

هذا هو أساسا نفس السؤال هذا السؤال.نفس النهج يعمل هنا من أجل الذاكرة وافرة للحصول على O(N) التعقيد.في الأساس مجرد متكرر في محاولة لوضع كل عدد صحيح إلى الموقع الصحيح ونرى ما لا يملك القيمة الصحيحة.

Answer 6

حسنا, انها حول ملف يحتوي على جميع 4 مليار صحيحة ما عدا واحدة!هذا هو الصيد في هذه الحالة.

1. وأنت تتحرك على طول قائمة من الأعداد الصحيحة ، حساب المجموع.
2. في النهاية حساب المبلغ كما لو كان هناك جميع الأعداد الصحيحة الحالي باستخدام الصيغة N * (N + 1) / 2
3. استخراج مجموع في (1) من المبلغ الذي يتم حسابه في (2).التي هي في عداد المفقودين صحيح.

على سبيل المثال:نفترض لدينا التسلسل التالي:9 3 2 8 4 10 6 1 7 (1 خلال 10 مع 5 في عداد المفقودين).ونحن نضيف الأعداد الصحيحة بالتتابع, نحصل على 9 + 3 + 2 + 8 + 4 + 10 + 6 + 1 + 7 = 50.مجموع الأعداد الصحيحة من 1 إلى 10 10 * (10 + 1) / 2 = 55.ولذلك المفقودين العدد 55 - 50 = 5.Q. E. D.