البحث الأسي

في علم الحاسوب ، يُعد البحث الأسي (ويُسمى أيضًا البحث المضاعف أو البحث المتسارع أو بحث ستروزيك ) ^{[ 1 ]} خوارزميةً ابتكرها جون بنتلي وأندرو تشي-تشيه ياو عام 1976، للبحث في قوائم مرتبة غير محدودة/لا نهائية. ^{[ 2 ]} توجد طرق عديدة لتنفيذ هذه الخوارزمية، وأكثرها شيوعًا هو تحديد نطاق يقع فيه مفتاح البحث وإجراء بحث ثنائي ضمن هذا النطاق. يتطلب هذا${\displaystyle O(\log i)}$الوقت، أين${\displaystyle i}$هو موضع مفتاح البحث في القائمة، إذا كان مفتاح البحث موجودًا في القائمة، أو الموضع الذي يجب أن يكون فيه مفتاح البحث، إذا لم يكن مفتاح البحث موجودًا في القائمة.

يمكن استخدام البحث الأسي أيضًا للبحث في القوائم المحدودة. بل قد يتفوق البحث الأسي على عمليات البحث التقليدية في القوائم المحدودة، مثل البحث الثنائي، عندما يكون العنصر المطلوب البحث عنه قريبًا من بداية المصفوفة. وذلك لأن البحث الأسي سيعمل في${\displaystyle O(\log i)}$الوقت، أين${\displaystyle i}$يمثل فهرس العنصر الذي يتم البحث عنه في القائمة، بينما يتم تشغيل البحث الثنائي في${\displaystyle O(\log n)}$الوقت، أين${\displaystyle n}$يمثل عدد العناصر في القائمة.

يُتيح البحث الأسي البحث في قائمة مُرتبة وغير محدودة عن قيمة مُدخلة مُحددة (مفتاح البحث). تتكون الخوارزمية من مرحلتين. تُحدد المرحلة الأولى نطاقًا يقع فيه مفتاح البحث إذا كان موجودًا في القائمة. في المرحلة الثانية، يُجرى بحث ثنائي على هذا النطاق. في المرحلة الأولى، وبافتراض أن القائمة مُرتبة تصاعديًا، تبحث الخوارزمية عن الأس الأول ، j ، حيث تكون القيمة 2j ^أكبر من مفتاح البحث. تُصبح هذه القيمة، 2j ^، الحد الأعلى للبحث الثنائي، بينما يُمثل الأس السابق للعدد 2، 2j ^{- 1} ، الحد الأدنى للبحث الثنائي. ^{[ 3 ]}

// تُعيد موضع المفتاح في المصفوفة arr ذات الطول size. template < typename T > int exponential_search ( T arr [], int size , T key ) { if ( size == 0 ) { return NOT_FOUND ; }int bound = 1 ; while ( bound < size && arr [ bound ] < key ) { bound *= 2 ; }return binary_search ( arr , key , bound / 2 , min ( bound , size )); }

في كل خطوة، تقارن الخوارزمية قيمة مفتاح البحث بقيمة المفتاح عند فهرس البحث الحالي. إذا كان العنصر عند الفهرس الحالي أصغر من مفتاح البحث، تُكرر الخوارزمية العملية، وتنتقل إلى فهرس البحث التالي بمضاعفته، ثم تحسب القوة التالية للعدد 2. ^{[ 3 ]} إذا كان العنصر عند الفهرس الحالي أكبر من مفتاح البحث، فإن الخوارزمية تعلم الآن أن مفتاح البحث، إن وُجد في القائمة، يقع في الفترة المُشكّلة من فهرس البحث السابق (2j ^{- 1} ) وفهرس البحث الحالي (2j ⁾ . بعد ذلك، يُجرى البحث الثنائي، وتكون النتيجة إما فشلًا إذا لم يكن مفتاح البحث موجودًا في القائمة، أو موضع مفتاح البحث في القائمة.

المرحلة الأولى من الخوارزمية تأخذ${\displaystyle O(\log i)}$الوقت، أين${\displaystyle i}$يمثل هذا الفهرس الذي سيُوضع فيه مفتاح البحث في القائمة. وذلك لأنه عند تحديد الحد الأعلى للبحث الثنائي، يتم تنفيذ حلقة while بدقة${\displaystyle \lceil \log(i)\rceil }$مرات. بما أن القائمة مرتبة، بعد مضاعفة فهرس البحث${\displaystyle \lceil \log(i)\rceil }$في بعض الأحيان، ستكون الخوارزمية عند فهرس بحث أكبر من أو يساوي i كما${\displaystyle 2^{\lceil \log(i)\rceil }\geq i}$وبالتالي، فإن المرحلة الأولى من الخوارزمية تأخذ${\displaystyle O(\log i)}$وقت.

يأخذ الجزء الثاني من الخوارزمية أيضًا${\displaystyle O(\log i)}$الوقت. بما أن المرحلة الثانية هي ببساطة بحث ثنائي، فإنها تستغرق وقتًا.${\displaystyle O(\log n)}$أين${\displaystyle n}$يمثل حجم الفترة التي يتم البحث فيها. سيكون حجم هذه الفترة 2j ^- 2j ^{- 1} حيث، كما هو موضح أعلاه، j =${\displaystyle \log i}$هذا يعني أن حجم الفترة التي يتم البحث فيها هو 2 ^{log i} - 2 ^{log i - 1} = 2 ^{log i - 1.} وهذا يعطينا زمن تشغيل قدره log  (2 ^{log i - 1} ) = log  ( i ) - 1 =${\displaystyle O(\log i)}$.

وهذا يعطي الخوارزمية وقت تشغيل إجمالي، يتم حسابه عن طريق جمع أوقات تشغيل المرحلتين، وهو:${\displaystyle O(\log i)}$+${\displaystyle O(\log i)}$= 2${\displaystyle O(\log i)}$=${\displaystyle O(\log i)}$.

اقترح بنتلي وياو عدة تعديلات على البحث الأسي. ^{[ 2 ]} تتضمن هذه التعديلات إجراء بحث ثنائي، بدلاً من البحث الأحادي، عند تحديد الحد الأعلى للبحث الثنائي في المرحلة الثانية من الخوارزمية. يؤدي هذا إلى تقسيم المرحلة الأولى من الخوارزمية إلى جزأين، مما يجعل الخوارزمية ثلاثية المراحل إجمالاً. تحدد المرحلة الأولى الجديدة قيمةً.${\displaystyle j'}$كما كان الحال من قبل، بحيث${\displaystyle 2^{j'}}$أكبر من مفتاح البحث و${\displaystyle 2^{j'/2}}$أقل من مفتاح البحث. سابقًا،${\displaystyle j'}$تم تحديدها بطريقة أحادية عن طريق حساب القوة التالية للعدد 2 (أي إضافة 1 إلى j ). في التباين، يُقترح أن${\displaystyle j'}$يتم مضاعفة العدد بدلاً من ذلك (على سبيل المثال، القفز من 2 ² إلى 2 ⁴ بدلاً من 2 ³ ). الأول${\displaystyle j'}$بحيث${\displaystyle 2^{j'}}$عندما تكون القيمة أكبر من مفتاح البحث، فإنها تشكل حدًا أعلى أقل دقة بكثير من ذي قبل. بمجرد أن يحدث هذا${\displaystyle j'}$إذا تم العثور على العنصر المطلوب، ينتقل البرنامج إلى مرحلته الثانية ويتم إجراء بحث ثنائي على الفترة التي تشكلها الخوارزمية.${\displaystyle j'/2}$و${\displaystyle j'}$مما يُعطي قيمة الأس الأعلى الأكثر دقة j . من هنا، تُجري المرحلة الثالثة من الخوارزمية البحث الثنائي على الفترة 2j ^{- 1} و2 ^j ، كما في السابق. أداء هذا التغيير هو${\displaystyle \lfloor \log i\rfloor +2\lfloor \log(\lfloor \log i\rfloor +1)\rfloor +1=O(\log i)}$.

قام بنتلي وياو بتعميم هذا التباين إلى تباين يتم فيه تنفيذ أي عدد، k ، من عمليات البحث الثنائي خلال المرحلة الأولى من الخوارزمية، مما ينتج عنه تباين البحث الثنائي المتداخل k . لا يتغير وقت التشغيل التقاربي بالنسبة لهذه التباينات، حيث يعمل في${\displaystyle O(\log i)}$الوقت، كما هو الحال مع خوارزمية البحث الأسي الأصلية.

كذلك، يمكن الحصول على بنية بيانات ذات نسخة مُحكمة من خاصية الإصبع الديناميكي عند استخدام نتيجة البحث الثنائي المتداخل k المذكورة أعلاه على مصفوفة مُرتبة. ^{[ 4 ]} باستخدام هذه البنية، يكون عدد المقارنات التي تُجرى أثناء البحث هو log  ( d ) + log  log  ( d ) + ... + O (log ^* d )، حيث d هو الفرق في الرتبة بين آخر عنصر تم الوصول إليه والعنصر الحالي الذي يتم الوصول إليه. 

خوارزمية تعتمد على زيادة نطاق البحث بشكل أُسّي تحل مشكلة المحاذاة الزوجية العالمية لـ${\displaystyle O(ns)}$، أين${\displaystyle n}$هو طول التسلسلات و${\displaystyle s}$هي مسافة التحرير بينهما. ^{[ 5 ] [ 6 ]}

• البحث الخطي
• البحث الثنائي
• بحث الاستيفاء
• البحث الثلاثي
• جدول التجزئة