البحث

البحث عن إبرة في كومة قش

أبسط طرق البحث هي ما نقوم به للعثور على إبرةٍ في كومة قش كما يقول المثل الدَّارج. إذا أردنا العثور على عنصرٍ في مجموعة عناصر ولا توجد بنية محدَّدة تمامًا في تلك المجموعة، فلا سبيل أمامنا سوى التحقُّق من كل عنصرٍ تلو الآخر إلى أن نجد العنصر الذي نبحث عنه أو نخفق في إيجاده بعد فرز كل العناصر واستنفادها.

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

لا نتعامل عادةً مع عناصر مادية في أجهزة الكمبيوتر، بل مع تمثيلات رقمية لها. وتأتي إحدى الطرق الشائعة لتمثيل مجموعات من البيانات على جهاز كمبيوتر في شكل «قائمة». والقائمة عبارة عن بنية بيانات تحتوي على مجموعةِ عناصر بطريقةٍ تمكِّننا من العثور على عنصر بناءً على العنصر الذي يسبقه. عادة ما يمكننا اعتبار أن القائمة تحوي «عناصر مترابطة»، حيث يشير كل عنصر إلى العنصر التالي حتى النهاية بحيث لا يشير العنصر الأخير إلى شيء. والمجاز ليس بعيدًا عن الواقع؛ لأن أجهزة الكمبيوتر تستخدم مواقع الذاكرة الداخلية لتخزين العناصر. وفي «القائمة المترابطة»، يحتوي كل عنصر على مكوِّنين هما: حمولة البيانات وموقع الذاكرة للعنصر التالي في القائمة. يُطلق على الموقع في الذاكرة الذي يحمل موقع الذاكرة لمكانٍ آخرَ في الذاكرة «المؤشر». لذلك يحتوي كل عنصر في القائمة المترابطة على مؤشرٍ للعنصر التالي. يُطلق على العنصر الأول في القائمة «رأس» القائمة. ويُطلق على العناصر في القائمة اسم «العُقَد» أيضًا. ولا تشير العقدة الأخيرة إلى أي عنصر آخر؛ ومِن ثَم نقول إنها تشير إلى «قيمة فارغة»؛ أي لا شيء على الكمبيوتر.

القائمة عبارة عن سلسلة عناصر، ولكن لا يلزم ترتيب السلسلة باستخدام معيار معيَّن. على سبيل المثال، فيما يلي قائمة تحتوي على بعض الحروف الأبجدية:

إذا كنَّا نبحث في عدد من العناصر، فأفضل شيء يمكن أن يحدث هو الوصول إلى العنصر الذي نبحث عنه في الحال، وهو ما سيحدث إذا كان العنصر هو رأس القائمة. أما أسوأ شيء يمكن أن يحدث، فهو أن يكون العنصر في نهاية القائمة أو ليس على القائمة على الإطلاق. عندئذٍ، سنضطر إلى تصفُّح كل عناصر . وهكذا يصبح أداء البحث التسلسلي بالقيمة .

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

يواجه الناس مشكلةً في ذلك في بعض الأحيان. إذا كنا نبحث عن ورقةٍ بين كومة كبيرة من الأوراق، فربما نشعر بالضجر من تصفُّح الأوراق الواحدة تلو الأخرى. بل ربما نفكِّر في مدى تعاسة الحظ التي سنُمنَى بها إن تبيَّن أن الورقة في نهاية كومة الورق! لذا نتوقَّف عن تصفُّح كومة الورق بالترتيب ونلقي نظرة خاطفة على نهاية الكومة. لا خطأ في إلقاء نظرة خاطفة على نهاية الكومة، ولكن الخطأ أن نعتقد أن تلك الطريقة تحسِّن من فرص الانتهاء من البحث بسرعة. إذا كانت الكومة ذات ترتيب عشوائي، فلا يوجد سببٌ لكي نعتقد أن الورقة التي نبحث عنها ليست في البداية أو النهاية أو جهة اليمين أو في المنتصف. كل المواضع محتملة على نحوٍ متساوٍ؛ لذا فالبدء من قمة الكومة وصولًا إلى قاعدتها يُعَد استراتيجية جيدة مثل أي استراتيجية أخرى تضمن تفقُّد كل عنصر مرة واحدة فقط. لكن عادة ما يكون الأسهل أن نتتبَّع ما بحثنا فيه إذا كنا نبحث بترتيب معيَّن بدلًا من التنقُّل بين العناصر بلا نظام؛ ولذا نفضِّل الالتزام بطريقة البحث التسلسلي.

كل هذا يصح ما دام لا يوجد سببٌ للتشكيك في أن العنصر الذي نبحث عنه في موضعٍ معيَّن. ولكن إذا لم يكن ذلك صحيحًا، فالأمور تتغيَّر ويمكننا الاستفادة من أي معلومات إضافية قد تكون متوافرة لدينا لتسريع عملية البحث.

تأثير ماثيو والبحث

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

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

قد يحدث ألَّا نعمل بالمعدل نفسه على كل المستندات. فقد نعود إلى بعضها مرارًا، وربما لا نلتفت إلى مستندات أخرى إلا نادرًا. وإذا استمررنا في وضع كل مستندٍ أعلى الكومة بعد العمل عليه، فسنكتشف بعد فترة أن المستندات الأكثر استخدامًا ستكون قريبة من القمة، بينما المستندات الأخرى الأقل استخدامًا اتجهت إلى القاعدة. تلك الطريقة مناسبة لنا؛ لأننا نقضي وقتًا أقلَّ في تحديد أماكن المستندات الكثيرة الاستخدام، ومِن ثَم يقل وقت العمل بوجه عام.

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

ما مدى قابلية تلك الاستراتيجية للتطبيق؟ يعتمد هذا على عدد المرات التي نلاحظ فيها مثل هذه الفروق في كثرة الاستخدام. وقد تبيَّن أن هذا يحدث كثيرًا. نعرف مقولة «الغني يزداد غنًى، والفقير يزداد فقرًا». إنها لا ترتبط بالأغنياء والفقراء فحسب. فالأمر نفسه يحدث في مجموعةٍ مذهلة من الجوانب في مختلف مجالات النشاط. وقد اتخذت الظاهرة اسمًا وهو «تأثير ماثيو» أو تأثير متَّى نسبة للآية التالية في إنجيل متَّى (٢٥: ٢٩): «لأن كلَّ مَن له يُعطى فيزدادُ، ومَن ليس له فالذي عنده يُؤخذ منه.»

تتحدَّث الآية عن السلع المادية؛ لذا لنفكر في الثروة لدقيقةٍ. لنفترض أنك تمتلك استادًا كبيرًا يسع ٨٠ ألف فرد. بإمكانك قياس متوسط أطوال الأفراد في الاستاد. قد تكون النتيجة في حدود ١٧٠ سنتيمترًا (٥ أقدام و٧ بوصات). تخيَّل أنك أخرجت فردًا بصورة عشوائية من الاستاد وأدخلت أطول شخص في العالم. هل سيختلف متوسط الطول؟ حتى إذا كان أطولُ شخص في العالم ٣ أمتار (علمًا بأن هذا الطول لم يُسجَّل حتى الآن)، فلن يتغيَّر متوسط الأطوال عن القيمة السابقة؛ فالفرق مع متوسط الأطوال السابق أقلُّ من واحد على عشرة من الملِّيمتر.

تخيَّل الآن أنك بدلًا من قياس متوسط الأطوال، تقيس متوسط الثروات. يمكن أن يكون متوسط ثروات الثمانين ألف فرد السابقين مليون دولار (نحن نفترض مجموعة ثرية). تعاود الآن إدخال شخص آخر بين أغنى أثرياء العالم. قد تبلغ ثروة ذلك الشخص ١٠٠ مليار دولار. هل تلك القيمة تُحدِث فارقًا؟ نعم، تُحدِث فارقًا، بل فارقًا كبيرًا. سيزيد المتوسط من مليون دولار إلى ٢٢٤٩٩٨٧٫٥ دولار، أو أكثر من الضعف. نعلم أن الثروة ليست موزَّعة بالتساوي على مستوى العالم، ولكن ربما لا نعلم مدى عدم التساوي في توزيعها. فالتفاوت في توزيع الثروة أكبر بكثير من القياسات الطبيعية مثل الأطوال.

يظهر الفارق نفسه في القدرات والمَلَكات في العديد من المواقع الأخرى. فهناك العديد من الممثلين لم تسمع بهم من قبل. وهناك بضعة نجوم يظهرون في العديد من الأفلام ويربحون ملايين الدولارات. كان عالِم الاجتماع روبرت كيه ميرتون هو مَن صاغ مصطلح «تأثير ماثيو» عام ١٩٦٨ حين لاحظ أن العلماء المشهورين يحظون بالتقدير لأعمالهم أكثرَ من زملائهم الأقل شهرة حتى لو كانت إسهاماتهم متماثلة. فكلما ذاع صيت العالِم حظي بشهرةٍ أوسع.

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

تُعَد طريقتا النقل إلى المقدمة وتبديل الموضع مثالين على «البحث الذاتي التنظيم»، الذي جاءت تسميته تلك من كون قائمة العناصر تُرتَّب مع تواتر عمليات البحث، وسوف تعكس مدى شيوع العناصر قيد البحث. وبناءً على مدى شيوع العنصر وسط العناصر الأخرى، قد يكون التوفير في الوقت كبيرًا. فبينما يمكن توقُّع أداء البحث التسلسلي بالقيمة ، يمكن أن يكون أداء البحث ذاتي التنظيم بطريقة النقل إلى المقدمة بالقيمة . إذا كان لدينا ما يقرب من مليون عنصر، تكون هذه القيمة هي الفرق بين مليون و٥٠٠٠٠ تقريبًا. قد تؤتي طريقة تبديل الموضع نتائجَ أفضل، لكنها تتطلب مزيدًا من الوقت لتحقيقها. والسبب في ذلك أن الطريقتين كلتيهما تتطلبان «فترة إحماء» تعلِن خلالها العناصرُ الشائعة عن نفسِها وتشقُّ طريقها نحو المقدمة. في طريقة النقل إلى المقدمة تقصُر فترة الإحماء، أما في طريقة تبديل الموضع فيستغرق الإحماء فترةً أطول، ولكننا نحصل على نتائجَ أفضل.²

كيبلر والسيارات والسكرتيرات

بعدما فقد عالِم الفلك الشهير يوهانس كيبلر (١٥٧١-١٦٣٠) زوجتَه بسبب الكوليرا عام ١٦١١، بدأ التخطيط للزواج مرةً أخرى. ونظرًا لكونه رجلًا منهجيًّا، لم يترك شيئًا للصدفة. وفي خطابٍ طويل أرسله إلى البارون ستراهليندورف، وصف العملية التي اتَّبعها. خطَّط كيبلر لإجراء مقابلات مع ١١ عروسًا محتملة قبل أن يتخذ قراره. وانجذب بشدة إلى المرشَّحة الخامسة، ولكنه انصرف عنها بسبب أصدقائه الذين اعترضوا على مكانتها الاجتماعية المتواضعة. ونصحوه بأن يعيد النظر في المرشَّحة الرابعة بدلًا منها. ولكنها رفضته. في النهاية، وبعد دراسة ١١ مرشَّحة، تزوَّج كيبلر المرشَّحة الخامسة، وهي سوزانا روتينجر البالغة من العمر ٢٤ عامًا.

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

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

يُعَد هذا مثالًا على «مسألة التوقُّف الأمثل». علينا أن نتخذ إجراءً وفي الوقت نفسه نحاول تعظيمَ عائدٍ ما أو تقليل تكلفةٍ ما. في هذا المثال، نريد أن نقرِّر شراء السيارة، حين يكون هذا القرار سيفضي إلى شراء أفضل سيارة يمكن شراؤها. إذا قرَّرنا في مرحلةٍ مبكرة للغاية، فربما نستقر على سيارةٍ أسوأ من السيارات التي لم نرَها بعد. وإذا قرَّرنا في مرحلةٍ متأخرة للغاية، قد نغتم حين نكتشف أننا قد رأينا أفضلَ سيارة ولكننا فقدناها. إذن متى يكون الوقت الأمثل للتوقُّف واتخاذ القرار؟

وُصِفت المشكلةُ نفسها بمزيد من الحدة تحت اسم «مسألة السكرتيرة». أنت تريد اختيار سكرتيرة من بين مجموعةٍ من المرشَّحات. يمكنك إجراء مقابلة مع المرشَّحات واحدة بواحدة. لكن يجب أن تتخذ قرارًا بالتوظيف من عدمه في نهاية كل مقابلة. وإذا رفضت مرشَّحة، لا يمكنك أن تغيِّر رأيك لاحقًا وتقدِّم لها عرضًا (قد تكون المرشَّحة جيدة للغاية ومِن ثَم ينتزعها شخص آخرُ للعمل لديه). كيف ستختار المرشَّحة؟

الإجابة بسيطة إلى حد الذهول. تجري المقابلة مع ٣٧ بالمائة من المرشَّحات وترفضهن جميعًا، ولكن مع الاحتفاظ بسجلٍ للأفضل من بينهن كمعيار استرشادي. يظهر العدد ٣٧ — الذي يبدو سحريًّا — لأن ٣٧٪ تساوي تقريبًا ، حيث تعبِّر عن عدد أويلر، الذي يساوي تقريبًا ٢٫٧١٨٢ (تعرَّفنا على عدد أويلر في الفصل الأول). ثم تجري المقابلات مع بقية المرشَّحات. تتوقَّف عند أول مرشحة تكون أفضل من المعيار الذي معك. هذه ستكون اختيارك. وبالصيغة الخوارزمية، إذا كان لديك من المرشَّحات:

• (١)
  احسب ، لإيجاد نسبة اﻟ ٣٧٪ من العدد من المرشَّحات.
• (٢)
  ادرس أول من المرشَّحات وارفضهن. ستستخدم أفضل واحدة منهن كمعيار استرشادي لك.
• (٣)

  واصل مع بقية المرشَّحات. اختر أول مرشَّحة تجدها أفضل من المعيار الذي معك، وتوقَّف.

لن تجد الخوارزمية المرشَّح الأفضل على الدوام؛ ففي النهاية، قد يكون المرشَّح الأفضل عمومًا هو المرشَّح المعياري الذي حدَّدته ضمن أول ٣٧ بالمائة، وسبق أن رفضته. ويمكن إثبات أنها ستجد لك المرشَّح الأفضل في ٣٧ بالمائة (مرة أخرى ) من جميع الحالات؛ إضافة إلى ذلك، لا توجد طريقة أخرى من شأنها أن تنجح في العثور على المرشَّح الأفضل في مزيد من الحالات. بعبارة أخرى، الخوارزمية هي أفضل الطرق التي يمكن تتبُّعها؛ وعلى الرغم من أنها قد لا تعطيك أفضل مرشَّح في ٦٣٪ من الحالات، فلا توجد استراتيجية أخرى تعطيك نتيجةً أفضل من تلك النتيجة.

بالعودة إلى السيارات، لنفترض أنك قرَّرت الذهاب إلى ١٠ معارض لتجارة السيارات. ينبغي أن نذهب إلى أول أربعة معارض وندوِّن ملحوظةً بأفضل عرض مقدَّم منها، دون شراء. بعد ذلك نبدأ في زيارة المعارض الستة المتبقية، وسنشتري من أول معْرض يقدِّم لنا عرضًا أفضلَ من العرض الذي دوَّناه (وسنتجاوز البقية حينئذٍ). ربما نكتشف أن المَعارض الستة جميعًا تقدِّم عروضًا أسوأ من الأربعة الأولى التي ذهبنا إليها من دون أن نشتري. ولكن لا توجد استراتيجيةٌ أفضلُ يمكن أن تعطينا احتمالاتٍ أفضل للحصول على أفضل صفقة.

لقد افترضنا أننا نريد العثور على أفضلِ مرشَّح محتمَل ولن نقبل بأقلَّ من ذلك. ولكن ماذا لو استطعنا القبول بشيءٍ أقلَّ في الحقيقة؟ هذا يعني أنه على الرغم من أننا نريد حقًّا أفضلَ سكرتيرة أو سيارة، فربما نقنع باختيارٍ آخرَ، وربما نسعد به وإن لم يكن قدْر سعادتنا لو اخترنا الأفضل. إذا وضعنا إطارًا للمسألة بهذا الشكل، فإن أفضلَ طريقة نحدِّد بها اختيارنا هي استخدام الخوارزميةِ نفسها السالفةِ الذكر، ولكن مع اختبار الجذر التربيعي لعدد المرشَّحين — — وإسقاطه. إذا فعلنا ذلك، فسوف تزيد احتمالية انتقاء الخيار الأفضل مع زيادة عدد المرشَّحين؛ فكلما زادت قيمة ، ارتفعت احتمالية انتقاء الخيار الأفضل إلى ١ (أي ١٠٠ بالمائة).³

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

تناولنا طرقَ البحث المختلفة وطابقناها مع مختلف السيناريوهات. والقاسم المشترك في كل هذه الطرق أن العناصر التي نتناولها تأتينا دون ترتيب محدَّد؛ وفي أفضل الحالات، نرتِّبها نحن تدريجيًّا حسب تكرار استخدامها في عمليةِ بحث ذاتية التنظيم. ولكن يتغيَّر الموقف تمامًا إذا كانت العناصر مرتَّبة منذ البداية.

في أيٍّ من النتيجتين الأخيرتين، يصبح المتبقي لدينا كومة تعادل نصف الكومة الأصلية على أقصى تقدير. إذا بدأنا بعددٍ فردي من المستندات، ولنقل العدد ، فإن ناتج قسمة العدد من المستندات إلى نصفين يعطينا جزأين، كل جزء يحتوي على العدد من العناصر (بغض النظر عن الجزء الكسري في عملية القسمة):

أما إذا كان لدينا عدد زوجي من العناصر، فسيعطينا ناتج القسمة جزأين؛ أحدهما يضم من العناصر، والآخر يضم من العناصر:

ما زلنا لم نعثر على ما نبحث عنه بعد، ولكننا في موقفٍ أفضلَ من ذي قبل بكثير؛ فقد صار لدينا عدد أقل بكثير من العناصر للبحث فيها. وهذا ما نفعله. نتحقق من المستند الأوسط في «العناصر المتبقية» ونكرِّر الإجراء.

في الشكل في الصفحة التالية، يمكنك أن ترى كيف تتطوَّر العملية بالنسبة إلى ١٦ عنصرًا نبحث فيها عن العنصر رقم ١٣٥. نحدِّد الحدود التي نبحث بداخلها والعنصر الأوسط باللون الرمادي.

في البداية، يكون نطاق البحث هو مجموعة العناصر كلها. ننتقل إلى العنصر الأوسط، الذي نجد أنه العنصر ٣٨٤. هذا العنصر أكبر من ١٣٥، ومِن ثَم نتجاهله، وكذلك كل العناصر الواقعة إلى يمينه. نأخذ العنصر الأوسط في العناصر المتبقية وهو العنصر ٧٢. هذا العنصر أصغر من ١٣٥، لذا نتجاهله وكذلك كل العناصر الواقعة على يساره. وبذلك يكون نطاق البحث قد تقلَّص إلى ثلاثة عناصر فقط. نأخذ العنصر الأوسط ونجد أنه العنصر المطلوب. لم يستغرق الأمر سوى ثلاث عمليات تحقُّق لإنهاء بحثنا، ولم نحتَج إلى التحقُّق حتى من ١٣ عنصرًا من بين ١٦ عنصرًا.

تصلح تلك الطريقة أيضًا إذا كنا نبحث عن شيءٍ غير موجود. يمكنك إدراك ذلك في الشكل التالي، حيث إننا نبحث في العناصر نفسها عن عنصر باسم ٥٢٠.

في هذه المرة، ٥٢٠ أكبر من ٣٨٤، ومِن ثَم نقيِّد البحث في النصف الأيمن من تلك العناصر. وهناك نجد أن العنصر الأوسط في النصف العلوي هو ٦١٣، وهو أكبر من ٥٢٠. عندئذٍ نقيِّد البحث في ثلاثة عناصر فقط، أوسطهم هو ٥٠٧. هذا العنصر أصغر من ٥٢٠. لذا نتجاهله ليتبقى لدينا عنصر واحد للتحقُّق منه ونكتشف أنه ليس العنصر الذي نريده. ومِن ثَم يمكننا إنهاء عملية البحث ونقول إن العنصر غير موجود. لم تستغرق العملية أكثر من ٤ عمليات تحقُّق.

بهذه الطريقة، نُقسِّم العناصر التي علينا البحث عنها على اثنين. ويُطلق على هذه الطريقة فرِّق تَسُد. تؤدي تلك الطريقة إلى تكرار عملية القسمة، ما يعطينا لوغاريتمًا كما رأينا في الفصل الأول. وتكرار القسمة على اثنين يعطينا لوغاريتمًا أساسه العدد اثنان. وفي أسوأ الحالات، سيستمر البحث الثنائي في قسمة العناصر مرارًا وتكرارًا حتى تستحيل عملية القسمة كما رأينا في مثال عملية البحث الفاشلة التي لم يُعثر فيها على العنصر. بالنسبة إلى العدد من العناصر، لا يمكن أن تتكرَّر عملية القسمة أكثر من من المرات؛ وعليه فإن قيمة تعقيد البحث الثنائي تساوي .

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

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

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

نحن هنا معنيون بالخوارزميات وليس بالبرمجة، ولكن اسمحوا للمؤلِّف أن يشارك بنصيحةٍ لمن يكتبون أو يريدون كتابة برامج الكمبيوتر. لا تيأس إذا وجدت نفسك بائسًا تتأمَّل سطرًا من الشيفرة البرمجية لا يفعل ما تعتقد أنه يجب أن يفعله. لا تفزع إذا أدركتَ في اليوم التالي أن الخطأ كان بالفعل أمام عينيك طوال الوقت. كيف لم ترَه؟ لست وحيدًا في ذلك. فهذا يحدث للجميع؛ بل يحدث للصفوة.

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