البحث الأسي
يحتاج البحث الثنائي إلى معرفة أين تنتهي القائمة قبل أن ينظر في منتصفها. أما البحث الأسي فلا: إنه يركض إلى الأمام بخطوات تكبر باستمرار حتى يتجاوز الهدف، ثم يطبّق البحث الثنائي على الخطوة الأخيرة. وهذا يجعله مثاليًا للقوائم المجهولة الطول، وسريعًا للقيم القريبة من البداية.
الفكرة
افحص القيمة في الموضع 1، ثم 2, 4, 8, 16 وهكذا، كل موضع ضعف الذي قبله. ما دامت القيمة هناك أصغر من الهدف، فلا بد أن يكون الهدف أبعد. وأول مرة تكون فيها القيمة ليست أصغر، يُحاصَر الهدف: فهو بعد الموضع السابق الذي فُحص وليس أبعد من هذا الموضع. وهذا النطاق مرتب، لذا يجد البحث الثنائي الهدف، أو يبيّن أنه غير موجود.
مثال
ابحث عن 23 في 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. في الموضع 1 القيمة 2، وفي الموضع 2 القيمة 5، وفي الموضع 4 القيمة 12، وكلها أصغر. وفي الموضع 8 القيمة 56، وهي أكبر، فلا يمكن أن تكون 23 إلا في المواضع من 5 إلى 7. يفحص البحث الثنائي منتصفها، الموضع 6، فيجد 23: أي 5 مقارنات، بينما يحتاج البحث الثنائي العادي إلى 3. والبحث عن 12 في القائمة نفسها يتوقف عند الموضع 4 بعد 3 مقارنات، أي أقل بواحدة من البحث الثنائي، وتُوجد 2 في الموضع 1 بمقارنة واحدة.
كم مقارنة
لهدف في الموضع i، تتوقف المضاعفة بعد نحو log₂ i خطوة، وتترك نطاقًا من أقل من i موضع، يغطيه البحث الثنائي في نحو log₂ i أخرى. لذا يكلّف البحث نحو 2 log₂ i مقارنة، مهما كان طول القائمة. وعندما يكون الهدف قرب البداية يتفوق ذلك على البحث الثنائي الذي يكلّف دائمًا نحو log₂ n. وعندما يكون قرب النهاية، يكلّف البحث الأسي حتى نحو الضعف. ولـ 40 قيمة، يبلغ متوسط التطبيق نحو 3 مقارنات للمواضع الخمسة الأولى ونحو 9 للخمسة الأخيرة، مقابل نحو 4.6 للبحث الثنائي.
طول مجهول، والركض
وصف Jon Bentley وAndrew Yao استراتيجية المضاعفة هذه عام 1976 للبحث غير المحدود: إيجاد قيمة في متتالية مرتبة بلا نهاية معروفة، مثل قائمة لا نهائية أو تدفق بيانات لا يمكنك إلا استطلاع مواضعه. والفكرة نفسها تسرّع الدمج. فعندما يظل أحد مقطعين مرتبين يفوز، ينتقل Timsort إلى وضع الركض (galloping): ينظر 1, 2, 4, 8 مواضع إلى الأمام في المقطع الآخر ليعرف أين تذهب القيمة التالية، بدلًا من التقدم موضعًا واحدًا في كل مرة.
جرّبه بنفسك
افتح التطبيق، واختر قيمة في «ابحث عن»، واضغط خطوة. تُبرَز كل نظرة إلى الموضع 1, 2, 4, 8 وهكذا؛ وما إن تكون قيمة ليست أصغر حتى يُظلَّل النطاق بين آخر موضعين ويتولى البحث الثنائي الأمر. ابحث عن قيمة صغيرة ثم عن قيمة كبيرة، وقارن العدد بمربع البحث الثنائي.
الأسئلة المتداولة
ما التعقيد الزمني للبحث الأسي؟
O(log i) لهدف في الموضع i، أي O(log n) على الأكثر لقائمة من n قيمة. ويحتاج إلى ذاكرة إضافية O(1) وقائمة مرتبة.
ما الفرق بين البحث الأسي والبحث الثنائي؟
يبدأ البحث الثنائي بالقائمة كلها ويحتاج إلى طولها. أما البحث الأسي فيجد أولًا بالمضاعفة نطاقًا يحتوي على الهدف، ثم يطبّق البحث الثنائي على هذا النطاق وحده. وهو أسرع عندما يكون الهدف قرب البداية، ويعمل دون معرفة الطول.
لماذا نضاعف الخطوة بدلًا من إضافة مقدار ثابت؟
إضافة خطوة ثابتة هي البحث بالقفز، الذي يحتاج إلى نحو n مقسومًا على الخطوة من النظرات لعبور القائمة. أما المضاعفة فتصل إلى الموضع i في نحو log₂ i نظرة، والنطاق الذي تتركه لا يزيد أبدًا على ضعف الحجم اللازم، لذا يبقى البحث الثنائي بعدها قصيرًا.
أين يُستخدم البحث الأسي؟
في البحث في بيانات مرتبة غير محدودة أو طويلة جدًا، وفي دمج المقاطع المرتبة (الركض في Timsort)، وفي إيجاد أول موضع يصبح فيه شرط ما صحيحًا حين لا يُعرف حد أعلى.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب البحث الأسي