البحث بالاستيفاء
عندما تبحث عن «يوسف» في دليل الهاتف، لا تفتحه في المنتصف: تفتحه قرب النهاية، لأن الياء آخر حروف الأبجدية. والبحث بالاستيفاء يفعل الشيء نفسه مع الأرقام. فهو يخمّن موضع الهدف من مقدار كبره، ومع البيانات الموزعة بالتساوي يكون هذا التخمين دقيقًا على نحو لافت.
الفكرة
يفحص البحث الثنائي المنتصف دائمًا، أيًّا كان ما يبحث عنه. أما البحث بالاستيفاء فيستخدم القيم. إذا كان الجزء المتبقي من القائمة يمتد من 10 إلى 100 وكان الهدف 70، فالهدف يقع على بُعد ثلثي المسافة بين أول قيمة وآخرها، لذا يفحص الموضع الذي يقع على بُعد ثلثي الطول. وبصيغة رياضية، يكون موضع الفحص lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). وبعد الفحص يحتفظ بالجزء الذي في الجهة الصحيحة، تمامًا كالبحث الثنائي، ثم يقدّر من جديد.
مثالان
في 10, 20, 30, 40, 50, 60, 70, 80, 90, 100، يفحص البحث عن 70 الموضع 7 مباشرة: وُجدت بعد 1 فحص، بينما يحتاج البحث الثنائي إلى 4. والآن خذ 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 وابحث عن 9. بسبب 999، يقع كل تقدير قرب البداية: يفحص البحث المواضع 1 و2 و3 وهكذا، موضعًا واحدًا في كل مرة، ويحتاج إلى 9 فحوص، بينما يحتاج البحث الثنائي إلى 3.
كم هو سريع
عندما تكون القيم موزعة بالتساوي، أو مسحوبة عشوائيًا من توزيع منتظم، يقلّص كل فحص الجزء المتبقي من نحو n إلى نحو √n. وهذا يعطي نحو log₂(log₂ n) فحص في المتوسط: نحو 5 حتى لمليار قيمة، مقابل 30 للبحث الثنائي. وعندما تكون القيم موزعة بغير تساوٍ شديد، قد لا يستبعد الفحص إلا قيمة واحدة، وتكون أسوأ حالة n فحص، أي بسوء البحث الخطي. ويكلّف كل فحص أيضًا عملية قسمة، لذا فهو مفيد عمليًا خاصةً عندما يكون الفحص مكلفًا، مثل القراءة من القرص.
التاريخ والأشكال الأخرى
وصف W. W. Peterson البحث بالاستيفاء عام 1957 للعثور على السجلات في وحدات التخزين ذات الوصول العشوائي. وأثبت Perl وItai وAvni عام 1978 أن متوسطه log log n للمفاتيح الموزعة بالتساوي. وتحمي النسخ العملية نفسها من البيانات السيئة بخلط خطوات ثنائية، مثل البحث الاستيفائي التسلسلي أو البحث الاستيفائي الثنائي، لتبقى أسوأ حالة قريبة من log n.
جرّبه بنفسك
افتح التطبيق، واختر قيمة في «ابحث عن»، واضغط «خطوة». يوضح كل فحص أين يقع الهدف بين القيمتين عند الطرفين وإلى أي موضع يشير ذلك. بدّل «التوزيع» إلى «متساوٍ» فتنتهي معظم عمليات البحث بفحص واحد؛ وبدّله إلى «منحاز» فتزحف الفحوص ببطء على بداية القائمة. ويعرض المربع الأخير عدد الخطوات التي يحتاجها البحث الثنائي للقيمة نفسها.
الأسئلة المتداولة
ما التعقيد الزمني للبحث بالاستيفاء؟
O(log log n) في المتوسط للقيم الموزعة بالتساوي، وO(n) في أسوأ حالة. ويحتاج إلى ذاكرة إضافية O(1) وقائمة مرتبة.
ما الفرق بين البحث بالاستيفاء والبحث الثنائي؟
يفحص البحث الثنائي دائمًا منتصف ما تبقى. أما البحث بالاستيفاء فيفحص حيث يُتوقع أن يكون الهدف، بناءً على القيمتين عند الطرفين. وهذا أفضل بكثير مع القيم الموزعة بالتساوي، وقد يكون أسوأ بكثير مع القيم المنحازة.
ما نوع البيانات المناسب للبحث بالاستيفاء؟
مفاتيح رقمية مرتبة موزعة بالتساوي إلى حد ما: معرّفات متتالية بفجوات قليلة، أو طوابع زمنية لأحداث منتظمة، أو مفاتيح مجزّأة. وهو يناسب البيانات التي يكون فيها الفحص مكلفًا والقليل من الحساب رخيصًا.
لماذا يتيح التطبيق توزيعات مختلفة؟
لأن التوزيع يحدد مدى جودة التقديرات. القيم المتساوية تجعل البحث بالاستيفاء يبدو سحريًا تقريبًا، والقيم المنحازة تكشف ضعفه. ومقارنتها بعدد خطوات البحث الثنائي هي أوضح طريقة لمعرفة متى تستخدم كلًّا منهما.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب البحث بالاستيفاء