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

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

تصور خوارزمية البحث الثنائي حيث 7 هي القيمة المستهدفة
فصل	خوارزمية البحث
هيكل البيانات	مصفوفة
الأداء في أسوأ الأحوال	O (سجل n )
أفضل أداء في الحالة	ا (1)
الأداء المتوسط	O (سجل n )
أسوأ حالة تعقيد الفضاء	ا (1)
أفضل	نعم

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

يتم تشغيل البحث الثنائي في وقت لوغاريتمي في أسوأ الحالات ، مما يؤدي إلى إجراء المقارنات، حيث هو عدد العناصر في المصفوفة. ^{[أ] [6]} البحث الثنائي أسرع من البحث الخطي باستثناء المصفوفات الصغيرة. ومع ذلك، يجب فرز المصفوفة أولاً حتى تتمكن من تطبيق البحث الثنائي. هناك هياكل بيانات متخصصة مصممة للبحث السريع، مثل جداول التجزئة ، والتي يمكن البحث فيها بكفاءة أكبر من البحث الثنائي. ومع ذلك، يمكن استخدام البحث الثنائي لحل مجموعة أوسع من المشكلات، مثل العثور على العنصر التالي الأصغر أو التالي الأكبر في المصفوفة بالنسبة للهدف حتى لو كان غائبًا عن المصفوفة. ${\displaystyle O(\log n)}$${\displaystyle n}$

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

يعمل البحث الثنائي على المصفوفات المصنفة. يبدأ البحث الثنائي بمقارنة عنصر في منتصف المصفوفة بقيمة الهدف. إذا كانت قيمة الهدف مطابقة للعنصر، يتم إرجاع موضعه في المصفوفة. إذا كانت قيمة الهدف أقل من العنصر، يستمر البحث في النصف السفلي من المصفوفة. إذا كانت قيمة الهدف أكبر من العنصر، يستمر البحث في النصف العلوي من المصفوفة. من خلال القيام بذلك، تستبعد الخوارزمية النصف الذي لا يمكن أن توجد فيه قيمة الهدف في كل تكرار. ^[7]

بالنظر إلى مجموعة من العناصر ذات القيم أو السجلات المرتبة بحيث و وقيمة الهدف ، يستخدم البرنامج الفرعي التالي البحث الثنائي للعثور على مؤشر في . ^[7]${\displaystyle A}$${\displaystyle n}$ ${\displaystyle A_{0},A_{1},A_{2},\ldots ,A_{n-1}}$${\displaystyle A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}}$${\displaystyle T}$${\displaystyle T}$${\displaystyle A}$

1. تعيين إلى و إلى .${\displaystyle L}$${\displaystyle 0}$${\displaystyle R}$${\displaystyle n-1}$
2. إذا ، تنتهي عملية البحث باعتبارها غير ناجحة.${\displaystyle L>R}$
3. اضبط (موضع العنصر الأوسط) على أرضية ، وهو أكبر عدد صحيح أقل من أو يساوي .${\displaystyle m}$${\displaystyle {\frac {L+R}{2}}}$${\displaystyle {\frac {L+R}{2}}}$
4. إذا ، اضبط على وانتقل إلى الخطوة 2.${\displaystyle A_{m}<T}$${\displaystyle L}$${\displaystyle m+1}$
5. إذا ، اضبط على وانتقل إلى الخطوة 2.${\displaystyle A_{m}>T}$${\displaystyle R}$${\displaystyle m-1}$
6. الآن تم الانتهاء من البحث، العودة .${\displaystyle A_{m}=T}$${\displaystyle m}$

يتتبع هذا الإجراء التكراري حدود البحث باستخدام المتغيرين و . ويمكن التعبير عن الإجراء في الكود الزائف على النحو التالي، حيث تظل أسماء المتغيرات وأنواعها كما هي أعلاه، وهي دالة الأرضية ، وتشير إلى قيمة محددة تنقل فشل البحث. ^[7]${\displaystyle L}$${\displaystyle R}$floorunsuccessful

دالة البحث الثنائي (A, n, T) هي
    ل := 0
    ر := ن − 1
    بينما L ≤ R
        م := الطابق((L + R) / 2)
        إذا كان A[m] < T فإن
            ل := م + 1
        وإلا إذا كان A[m] > T فإن
            ر := م − 1
        وإلا :
             العودة م
     العودة غير ناجحة

بدلاً من ذلك، قد تأخذ الخوارزمية الحد الأقصى . وقد يؤدي هذا إلى تغيير النتيجة إذا ظهرت القيمة المستهدفة أكثر من مرة في المصفوفة. ${\displaystyle {\frac {L+R}{2}}}$

في الإجراء أعلاه، تتحقق الخوارزمية مما إذا كان العنصر الأوسط ( ) مساويًا للهدف ( ) في كل تكرار. بعض التنفيذات تتجاهل هذا الفحص أثناء كل تكرار. ستنفذ الخوارزمية هذا الفحص فقط عندما يتبقى عنصر واحد (عندما ). يؤدي هذا إلى حلقة مقارنة أسرع، حيث يتم إزالة مقارنة واحدة لكل تكرار، بينما يتطلب الأمر تكرارًا واحدًا فقط في المتوسط. ^[8]${\displaystyle m}$${\displaystyle T}$${\displaystyle L=R}$

نشر هيرمان بوتينبروتش أول تنفيذ لاستبعاد هذا الاختبار في عام 1962. ^{[8] [9]}

1. تعيين إلى و إلى .${\displaystyle L}$${\displaystyle 0}$${\displaystyle R}$${\displaystyle n-1}$
2. بينما ، ${\displaystyle L\neq R}$
   1. اضبط (موضع العنصر الأوسط) على سقف ، وهو أصغر عدد صحيح أكبر من أو يساوي .${\displaystyle m}$${\displaystyle {\frac {L+R}{2}}}$${\displaystyle {\frac {L+R}{2}}}$
   2. إذا تم ضبطه على .${\displaystyle A_{m}>T}$${\displaystyle R}$${\displaystyle m-1}$
   3. وإلا؛ يتم ضبطه على .${\displaystyle A_{m}\leq T}$${\displaystyle L}$${\displaystyle m}$
3. الآن ، تم الانتهاء من البحث. إذا ، ارجع . وإلا، تنتهي عملية البحث باعتبارها غير ناجحة.${\displaystyle L=R}$${\displaystyle A_{L}=T}$${\displaystyle L}$

أين ceilتوجد دالة السقف، الكود الزائف لهذه النسخة هو:

دالة binary_search_alternative(A, n, T) هي
    ل := 0
    ر := ن − 1
    بينما L != R
        م := السقف((L + R) / 2)
        إذا كان A[m] > T فإن
            ر := م − 1
        آخر :
            ل := م
    إذا A[L] = T ، قم 
        بإرجاع L،
     إرجاع غير ناجح

قد يعيد الإجراء أي فهرس يكون عنصره مساويًا لقيمة الهدف، حتى إذا كانت هناك عناصر مكررة في المصفوفة. على سبيل المثال، إذا كانت المصفوفة المراد البحث فيها هي وكان الهدف هو ، فسيكون من الصحيح أن تعيد الخوارزمية إما العنصر الرابع (الفهرس 3) أو الخامس (الفهرس 4). سيعيد الإجراء العادي العنصر الرابع (الفهرس 3) في هذه الحالة. لا يعيد دائمًا التكرار الأول (ضع في اعتبارك أيهما لا يزال يعيد العنصر الرابع). ومع ذلك، من الضروري أحيانًا العثور على العنصر الموجود في أقصى اليسار أو أقصى اليمين لقيمة هدف مكررة في المصفوفة. في المثال أعلاه، يكون العنصر الرابع هو العنصر الموجود في أقصى اليسار للقيمة 4، بينما يكون العنصر الخامس هو العنصر الموجود في أقصى اليمين للقيمة 4. سيعيد الإجراء البديل أعلاه دائمًا فهرس العنصر الموجود في أقصى اليمين إذا كان مثل هذا العنصر موجودًا. ^[9]${\displaystyle [1,2,3,4,4,5,6,7]}$${\displaystyle 4}$${\displaystyle [1,2,4,4,4,5,6,7]}$

للعثور على العنصر الموجود في أقصى اليسار، يمكن استخدام الإجراء التالي: ^[10]

1. تعيين إلى و إلى .${\displaystyle L}$${\displaystyle 0}$${\displaystyle R}$${\displaystyle n}$
2. بينما ، ${\displaystyle L<R}$
   1. اضبط (موضع العنصر الأوسط) على أرضية ، وهو أكبر عدد صحيح أقل من أو يساوي .${\displaystyle m}$${\displaystyle {\frac {L+R}{2}}}$${\displaystyle {\frac {L+R}{2}}}$
   2. إذا تم ضبطه على .${\displaystyle A_{m}<T}$${\displaystyle L}$${\displaystyle m+1}$
   3. وإلا؛ يتم ضبطه على .${\displaystyle A_{m}\geq T}$${\displaystyle R}$${\displaystyle m}$
3. يعود .${\displaystyle L}$

إذا و ، فإن العنصر الموجود في أقصى اليسار والذي يساوي . حتى إذا لم يكن في المصفوفة، فإن رتبة في المصفوفة، أو عدد العناصر في المصفوفة التي تكون أقل من . ${\displaystyle L<n}$${\displaystyle A_{L}=T}$${\displaystyle A_{L}}$${\displaystyle T}$${\displaystyle T}$${\displaystyle L}$${\displaystyle T}$${\displaystyle T}$

أين floorتوجد دالة الأرضية، الكود الزائف لهذه النسخة هو:

دالة binary_search_leftmost(A, n, T):
    ل := 0
    ر := ن
    بينما L < R:
        م := الطابق((L + R) / 2)
        إذا كان A[m] < T:
            ل := م + 1
        آخر :
            ر := م
    العودة ل

للعثور على العنصر الموجود في أقصى اليمين، يمكن استخدام الإجراء التالي: ^[10]

1. تعيين إلى و إلى .${\displaystyle L}$${\displaystyle 0}$${\displaystyle R}$${\displaystyle n}$
2. بينما ، ${\displaystyle L<R}$
   1. اضبط (موضع العنصر الأوسط) على أرضية ، وهو أكبر عدد صحيح أقل من أو يساوي .${\displaystyle m}$${\displaystyle {\frac {L+R}{2}}}$${\displaystyle {\frac {L+R}{2}}}$
   2. إذا تم ضبطه على .${\displaystyle A_{m}>T}$${\displaystyle R}$${\displaystyle m}$
   3. وإلا؛ يتم ضبطه على .${\displaystyle A_{m}\leq T}$${\displaystyle L}$${\displaystyle m+1}$
3. يعود .${\displaystyle R-1}$

إذا و ، فإن العنصر الموجود في أقصى اليمين يساوي . حتى إذا لم يكن في المصفوفة، فإن عدد العناصر في المصفوفة التي تكون أكبر من . ${\displaystyle R>0}$${\displaystyle A_{R-1}=T}$${\displaystyle A_{R-1}}$${\displaystyle T}$${\displaystyle T}$${\displaystyle n-R}$${\displaystyle T}$

أين floorتوجد دالة الأرضية، الكود الزائف لهذه النسخة هو:

دالة binary_search_rightmost(A, n, T):
    ل := 0
    ر := ن
    بينما L < R:
        م := الطابق((L + R) / 2)
        إذا كان A[m] > T:
            ر := م
        آخر :
            ل := م + 1
    العودة R - 1

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

• يمكن إجراء استعلامات الرتبة باستخدام الإجراء الخاص بالعثور على العنصر الموجود في أقصى اليسار. يتم إرجاع عدد العناصر الأقل من القيمة المستهدفة بواسطة الإجراء. ^[11]
• يمكن إجراء استعلامات السلف باستخدام استعلامات الرتبة. إذا كانت رتبة القيمة المستهدفة هي ، فإن سابقتها هي  . ^[12]${\displaystyle r}$${\displaystyle r-1}$
• بالنسبة لاستعلامات الخلف، يمكن استخدام إجراء العثور على العنصر الموجود في أقصى اليمين. إذا كانت نتيجة تشغيل الإجراء لقيمة الهدف هي ، فإن خليفة قيمة الهدف هو  . ^[12]${\displaystyle r}$${\displaystyle r+1}$
• أقرب جار للقيمة المستهدفة هو إما سابقتها أو خليفتها، أيهما أقرب.
• كما أن استعلامات النطاق واضحة ومباشرة. ^[12] بمجرد معرفة رتب القيمتين، فإن عدد العناصر الأكبر من أو تساوي القيمة الأولى والأقل من الثانية هو الفرق بين الرتبتين. يمكن تعديل هذا العدد لأعلى أو لأسفل بمقدار واحد وفقًا لما إذا كان يجب اعتبار نقاط نهاية النطاق جزءًا من النطاق وما إذا كانت المصفوفة تحتوي على إدخالات تطابق تلك النقاط النهائية. ^[13]

من حيث عدد المقارنات، يمكن تحليل أداء البحث الثنائي من خلال عرض تشغيل الإجراء على شجرة ثنائية. العقدة الجذرية للشجرة هي العنصر الأوسط من المصفوفة. العنصر الأوسط للنصف السفلي هو العقدة الفرعية اليسرى للجذر، والعنصر الأوسط للنصف العلوي هو العقدة الفرعية اليمنى للجذر. يتم بناء بقية الشجرة بطريقة مماثلة. بدءًا من العقدة الجذرية، يتم اجتياز الأشجار الفرعية اليسرى أو اليمنى اعتمادًا على ما إذا كانت القيمة المستهدفة أقل أو أكثر من العقدة قيد النظر. ^{[6] [14]}

في أسوأ الحالات، يقوم البحث الثنائي بإجراء تكرارات لحلقة المقارنة، حيث يشير الترميز إلى دالة الحد الأدنى التي تنتج أكبر عدد صحيح أقل من أو يساوي الوسيطة، وهو اللوغاريتم الثنائي . وذلك لأن أسوأ الحالات يتم الوصول إليها عندما يصل البحث إلى أعمق مستوى في الشجرة، وهناك دائمًا مستويات في الشجرة لأي بحث ثنائي. ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$${\textstyle \lfloor \cdot \rfloor }$${\textstyle \log _{2}}$${\textstyle \lfloor \log _{2}(n)+1\rfloor }$

قد يتم الوصول إلى أسوأ حالة أيضًا عندما لا يكون العنصر المستهدف موجودًا في المصفوفة. إذا كان أقل من قوة اثنين بمقدار واحد، فهذه هي الحالة دائمًا. بخلاف ذلك، قد يقوم البحث بإجراء تكرارات إذا وصل البحث إلى أعمق مستوى في الشجرة. ومع ذلك، قد يقوم بإجراء تكرارات ، وهي أقل بمقدار واحد من أسوأ حالة، إذا انتهى البحث عند ثاني أعمق مستوى في الشجرة. ^[15]${\textstyle n}$${\textstyle \lfloor \log _{2}(n)+1\rfloor }$${\textstyle \lfloor \log _{2}(n)\rfloor }$

في المتوسط، بافتراض أن احتمالية البحث عن كل عنصر متساوية، يقوم البحث الثنائي بإجراء التكرارات عندما يكون العنصر المستهدف في المصفوفة. وهذا يساوي تقريبًا التكرارات. عندما لا يكون العنصر المستهدف في المصفوفة، يقوم البحث الثنائي بإجراء التكرارات في المتوسط، بافتراض أن احتمالية البحث في النطاق بين العناصر وخارجها متساوية. ^[14]${\displaystyle \lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n}$${\displaystyle \log _{2}(n)-1}$${\displaystyle \lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)}$

في أفضل الأحوال، عندما تكون القيمة المستهدفة هي العنصر الأوسط في المصفوفة، يتم إرجاع موضعها بعد تكرار واحد. ^[16]

من حيث التكرارات، لا يمكن لأي خوارزمية بحث تعمل فقط عن طريق مقارنة العناصر أن تُظهر أداءً متوسطًا وأسوأ حالة أفضل من البحث الثنائي. تحتوي شجرة المقارنة التي تمثل البحث الثنائي على أقل عدد ممكن من المستويات حيث يتم ملء كل مستوى أعلى من أدنى مستوى في الشجرة بالكامل. ^[ب] بخلاف ذلك، يمكن لخوارزمية البحث التخلص من عدد قليل من العناصر في التكرار، مما يزيد من عدد التكرارات المطلوبة في المتوسط ​​​​وأسوأ حالة. هذا هو الحال بالنسبة لخوارزميات البحث الأخرى القائمة على المقارنات، حيث على الرغم من أنها قد تعمل بشكل أسرع على بعض قيم الهدف، فإن الأداء المتوسط ​​​​لجميع العناصر يكون أسوأ من البحث الثنائي. من خلال تقسيم المصفوفة إلى نصفين، يضمن البحث الثنائي أن يكون حجم كلتا المصفوفتين الفرعيتين متشابهًا قدر الإمكان. ^[14]

يتطلب البحث الثنائي ثلاثة مؤشرات إلى العناصر، والتي قد تكون مؤشرات مصفوفة أو مؤشرات إلى مواقع الذاكرة، بغض النظر عن حجم المصفوفة. وبالتالي، فإن تعقيد المساحة للبحث الثنائي يكمن في نموذج ذاكرة الوصول العشوائي للكلمات. ${\displaystyle O(1)}$

يعتمد متوسط ​​عدد التكرارات التي يتم إجراؤها بواسطة البحث الثنائي على احتمالية البحث عن كل عنصر. يختلف متوسط ​​الحالة لعمليات البحث الناجحة عن عمليات البحث غير الناجحة. سيتم افتراض أن كل عنصر من المرجح أن يتم البحث عنه بنجاح. بالنسبة لعمليات البحث غير الناجحة، سيتم افتراض أن الفواصل بين العناصر وخارجها من المرجح أن يتم البحث عنها بنفس القدر. متوسط ​​الحالة لعمليات البحث الناجحة هو عدد التكرارات المطلوبة للبحث عن كل عنصر مرة واحدة بالضبط، مقسومًا على ، عدد العناصر. متوسط ​​الحالة لعمليات البحث غير الناجحة هو عدد التكرارات المطلوبة للبحث عن عنصر داخل كل فترة مرة واحدة بالضبط، مقسومًا على الفواصل. ^[14]${\displaystyle n}$${\displaystyle n+1}$

في تمثيل الشجرة الثنائية، يمكن تمثيل البحث الناجح بمسار من الجذر إلى العقدة المستهدفة، يسمى المسار الداخلي . طول المسار هو عدد الحواف (الاتصالات بين العقد) التي يمر بها المسار. عدد التكرارات التي يتم إجراؤها بواسطة البحث، بشرط أن يكون للمسار المقابل طول ، هو حساب التكرار الأولي. طول المسار الداخلي هو مجموع أطوال جميع المسارات الداخلية الفريدة. نظرًا لوجود مسار واحد فقط من الجذر إلى أي عقدة واحدة، فإن كل مسار داخلي يمثل بحثًا عن عنصر معين. إذا كان هناك عناصر، وهو عدد صحيح موجب، وطول المسار الداخلي هو ، فإن متوسط ​​عدد التكرارات لبحث ناجح ، مع إضافة التكرار الواحد لحساب التكرار الأولي. ^[14]${\displaystyle l}$${\displaystyle l+1}$${\displaystyle n}$${\displaystyle I(n)}$${\displaystyle T(n)=1+{\frac {I(n)}{n}}}$

نظرًا لأن البحث الثنائي هو الخوارزمية المثلى للبحث باستخدام المقارنات، فإن هذه المشكلة تقتصر على حساب الحد الأدنى لطول المسار الداخلي لجميع الأشجار الثنائية التي تحتوي على عقد، والذي يساوي: ^[17]${\displaystyle n}$

${\displaystyle I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor }$

على سبيل المثال، في مصفوفة مكونة من 7 عناصر، يتطلب الجذر تكرارًا واحدًا، ويتطلب العنصران الموجودان أسفل الجذر تكرارين، وتتطلب العناصر الأربعة الموجودة أسفله ثلاث تكرارات. في هذه الحالة، يكون طول المسار الداخلي: ^[17]

${\displaystyle \sum _{k=1}^{7}\left\lfloor \log _{2}(k)\right\rfloor =0+2(1)+4(2)=2+8=10}$

سيتم حساب متوسط ​​عدد التكرارات بناءً على معادلة الحالة المتوسطة. يمكن تبسيط المجموع إلى: ^[14]${\displaystyle 1+{\frac {10}{7}}=2{\frac {3}{7}}}$${\displaystyle I(n)}$

${\displaystyle I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor =(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}$

استبدال المعادلة لـ في المعادلة لـ : ^[14]${\displaystyle I(n)}$${\displaystyle T(n)}$

${\displaystyle T(n)=1+{\frac {(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}{n}}=\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n}$

بالنسبة للعدد الصحيح ، فإن هذا يعادل معادلة الحالة المتوسطة في البحث الناجح المحدد أعلاه. ${\displaystyle n}$

يمكن تمثيل عمليات البحث غير الناجحة عن طريق زيادة الشجرة بالعقد الخارجية ، والتي تشكل شجرة ثنائية ممتدة . إذا كانت العقدة الداخلية، أو العقدة الموجودة في الشجرة، بها أقل من عقدتين فرعيتين، فسيتم إضافة عقد فرعية إضافية، تسمى العقد الخارجية، بحيث يكون لكل عقدة داخلية طفلان. من خلال القيام بذلك، يمكن تمثيل البحث غير الناجح كمسار إلى عقدة خارجية، حيث يكون العنصر الأصلي هو العنصر الوحيد المتبقي أثناء التكرار الأخير. المسار الخارجي هو مسار من الجذر إلى عقدة خارجية. طول المسار الخارجي هو مجموع أطوال جميع المسارات الخارجية الفريدة. إذا كان هناك عناصر، وهو عدد صحيح موجب، وكان طول المسار الخارجي هو ، فإن متوسط ​​عدد التكرارات لعملية بحث غير ناجحة ، مع إضافة تكرار واحد لحساب التكرار الأولي. يتم تقسيم طول المسار الخارجي على بدلاً من لأن هناك مسارات خارجية، تمثل الفواصل بين عناصر المصفوفة وخارجها. ^[14]${\displaystyle n}$${\displaystyle E(n)}$${\displaystyle T'(n)={\frac {E(n)}{n+1}}}$${\displaystyle n+1}$${\displaystyle n}$${\displaystyle n+1}$

يمكن تقليص هذه المشكلة على نحو مماثل إلى تحديد الحد الأدنى لطول المسار الخارجي لجميع الأشجار الثنائية التي تحتوي على عقد. بالنسبة لجميع الأشجار الثنائية، يكون طول المسار الخارجي مساويًا لطول المسار الداخلي زائدًا . ^[17] استبدال المعادلة بـ : ^[14]${\displaystyle n}$${\displaystyle 2n}$${\displaystyle I(n)}$

${\displaystyle E(n)=I(n)+2n=\left[(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2\right]+2n=(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}}$

من خلال استبدال المعادلة الخاصة بـ في المعادلة الخاصة بـ ، يمكن تحديد الحالة المتوسطة لعمليات البحث غير الناجحة: ^[14]${\displaystyle E(n)}$${\displaystyle T'(n)}$

${\displaystyle T'(n)={\frac {(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}}{(n+1)}}=\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)}$

كل تكرار لإجراء البحث الثنائي المحدد أعلاه يقوم بإجراء مقارنة واحدة أو اثنتين، للتحقق مما إذا كان العنصر الأوسط مساويًا للهدف في كل تكرار. وبافتراض أن احتمالية البحث عن كل عنصر متساوية، فإن كل تكرار يقوم بإجراء 1.5 مقارنة في المتوسط. يتحقق أحد أشكال الخوارزمية مما إذا كان العنصر الأوسط مساويًا للهدف في نهاية البحث. وفي المتوسط، يؤدي هذا إلى إزالة نصف مقارنة من كل تكرار. وهذا يقلل قليلاً من الوقت المستغرق لكل تكرار على معظم أجهزة الكمبيوتر. ومع ذلك، فإنه يضمن أن يستغرق البحث الحد الأقصى من التكرارات، في المتوسط ​​إضافة تكرار واحد إلى البحث. ولأن حلقة المقارنة يتم إجراؤها مرات فقط في أسوأ الأحوال، فإن الزيادة الطفيفة في الكفاءة لكل تكرار لا تعوض عن التكرار الإضافي لجميع العناصر باستثناء العناصر الكبيرة جدًا . ^{[ج] [18] [19]}${\textstyle \lfloor \log _{2}(n)+1\rfloor }$${\textstyle n}$

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

في معظم بنيات الكمبيوتر، يحتوي المعالج على ذاكرة تخزين مؤقتة منفصلة عن ذاكرة الوصول العشوائي . ونظرًا لوجودها داخل المعالج نفسه، فإن الوصول إلى ذاكرة التخزين المؤقت يكون أسرع كثيرًا ولكنها تخزن عادةً بيانات أقل بكثير من ذاكرة الوصول العشوائي. لذلك، تخزن معظم المعالجات مواقع الذاكرة التي تم الوصول إليها مؤخرًا، إلى جانب مواقع الذاكرة القريبة منها. على سبيل المثال، عند الوصول إلى عنصر مصفوفة، قد يتم تخزين العنصر نفسه مع العناصر المخزنة بالقرب منه في ذاكرة الوصول العشوائي، مما يجعل الوصول إلى عناصر المصفوفة القريبة من بعضها البعض ( موقع المرجع ) أسرع. في المصفوفة المرتبة، يمكن للبحث الثنائي القفز إلى مواقع ذاكرة بعيدة إذا كانت المصفوفة كبيرة، على عكس الخوارزميات (مثل البحث الخطي والفحص الخطي في جداول التجزئة ) التي تصل إلى العناصر بالتسلسل. وهذا يضيف قليلاً إلى وقت تشغيل البحث الثنائي للمصفوفات الكبيرة على معظم الأنظمة. ^[20]

تعتبر المصفوفات المصنفة مع البحث الثنائي حلاً غير فعال للغاية عندما تتداخل عمليات الإدخال والحذف مع الاسترجاع، مما يستغرق وقتًا لكل عملية من هذا القبيل. بالإضافة إلى ذلك، يمكن للمصفوفات المصنفة أن تعقد استخدام الذاكرة خاصةً عندما يتم إدخال العناصر غالبًا في المصفوفة. ^[21] هناك هياكل بيانات أخرى تدعم الإدراج والحذف بكفاءة أكبر بكثير. يمكن استخدام البحث الثنائي لإجراء المطابقة الدقيقة وعضوية المجموعة (تحديد ما إذا كانت قيمة الهدف موجودة في مجموعة من القيم). هناك هياكل بيانات تدعم المطابقة الدقيقة الأسرع وعضوية المجموعة. ومع ذلك، على عكس العديد من مخططات البحث الأخرى، يمكن استخدام البحث الثنائي للمطابقة التقريبية الفعالة، وعادةً ما يتم إجراء مثل هذه المطابقات في الوقت المناسب بغض النظر عن نوع أو بنية القيم نفسها. ^[22] بالإضافة إلى ذلك، هناك بعض العمليات، مثل العثور على أصغر وأكبر عنصر، والتي يمكن إجراؤها بكفاءة على مصفوفة مرتبة. ^[11]${\textstyle O(n)}$${\textstyle O(\log n)}$

البحث الخطي هو خوارزمية بحث بسيطة تتحقق من كل سجل حتى تجد القيمة المستهدفة. يمكن إجراء البحث الخطي على قائمة مرتبطة، مما يسمح بالإدراج والحذف بشكل أسرع من المصفوفة. البحث الثنائي أسرع من البحث الخطي للمصفوفات المفرزة إلا إذا كانت المصفوفة قصيرة، على الرغم من أن المصفوفة تحتاج إلى فرز مسبقًا. ^{[د] [24]} تتطلب جميع خوارزميات الفرز القائمة على مقارنة العناصر، مثل الفرز السريع والفرز بالدمج ، مقارنات على الأقل في أسوأ الحالات. ^[25] على عكس البحث الخطي، يمكن استخدام البحث الثنائي للمطابقة التقريبية الفعالة. هناك عمليات مثل العثور على أصغر وأكبر عنصر يمكن إجراؤها بكفاءة على مصفوفة مرتبة ولكن ليس على مصفوفة غير مرتبة. ^[26]${\textstyle O(n\log n)}$

شجرة البحث الثنائية هي بنية بيانات شجرة ثنائية تعمل على أساس مبدأ البحث الثنائي. يتم ترتيب سجلات الشجرة بترتيب مرتب، ويمكن البحث عن كل سجل في الشجرة باستخدام خوارزمية مشابهة للبحث الثنائي، وتستغرق وقتًا لوغاريتميًا متوسطًا. تتطلب عملية الإدراج والحذف أيضًا وقتًا لوغاريتميًا متوسطًا في أشجار البحث الثنائية. يمكن أن يكون هذا أسرع من عملية الإدراج والحذف الخطية للمصفوفات المفرزة، وتحتفظ الأشجار الثنائية بالقدرة على إجراء جميع العمليات الممكنة على مصفوفة مفرزة، بما في ذلك الاستعلامات النطاقية والتقريبية. ^{[22] [27]}

ومع ذلك، فإن البحث الثنائي يكون عادةً أكثر كفاءة في البحث حيث من المرجح أن تكون أشجار البحث الثنائي غير متوازنة بشكل كامل، مما يؤدي إلى أداء أسوأ قليلاً من البحث الثنائي. وهذا ينطبق حتى على أشجار البحث الثنائي المتوازنة ، أشجار البحث الثنائي التي توازن عقدها الخاصة، لأنها نادرًا ما تنتج الشجرة بأقل عدد ممكن من المستويات. باستثناء أشجار البحث الثنائي المتوازنة، قد تكون الشجرة غير متوازنة بشدة مع وجود عدد قليل من العقد الداخلية مع طفلين، مما يؤدي إلى اقتراب متوسط ​​​​وقت البحث وأسوأ حالة من المقارنات. ^[هـ] تشغل أشجار البحث الثنائي مساحة أكبر من المصفوفات المصنفة. ^[29]${\textstyle n}$

تلائم أشجار البحث الثنائية البحث السريع في الذاكرة الخارجية المخزنة على الأقراص الصلبة، حيث يمكن هيكلة أشجار البحث الثنائية بكفاءة في أنظمة الملفات. تعمم شجرة B هذه الطريقة في تنظيم الشجرة. تُستخدم أشجار B بشكل متكرر لتنظيم التخزين طويل الأمد مثل قواعد البيانات وأنظمة الملفات . ^{[30] [31]}

لتنفيذ المصفوفات الترابطية ، تكون جداول التجزئة ، وهي بنية بيانات تربط المفاتيح بالسجلات باستخدام دالة تجزئة ، أسرع بشكل عام من البحث الثنائي على مصفوفة مرتبة من السجلات. ^[32] تتطلب معظم تطبيقات جدول التجزئة وقتًا ثابتًا مستهلكًا فقط في المتوسط. ^{[f] [34]} ومع ذلك، فإن التجزئة ليست مفيدة للمطابقات التقريبية، مثل حساب المفتاح التالي الأصغر والأكبر والأقرب، حيث أن المعلومات الوحيدة المقدمة في بحث فاشل هي أن الهدف غير موجود في أي سجل. ^[35] يعد البحث الثنائي مثاليًا لمثل هذه المطابقات، حيث يتم إجراؤها في وقت لوغاريتمي. يدعم البحث الثنائي أيضًا المطابقات التقريبية. يمكن إجراء بعض العمليات، مثل العثور على أصغر وأكبر عنصر، بكفاءة على المصفوفات المرتبة ولكن ليس على جداول التجزئة. ^[22]

هناك مشكلة مرتبطة بالبحث وهي عضوية المجموعة . يمكن أيضًا استخدام أي خوارزمية تقوم بالبحث، مثل البحث الثنائي، لعضوية المجموعة. هناك خوارزميات أخرى أكثر ملاءمة لعضوية المجموعة. تعد مجموعة البتات هي الأبسط، ومفيدة عندما يكون نطاق المفاتيح محدودًا. إنها تخزن بشكل مضغوط مجموعة من البتات ، حيث يمثل كل بت مفتاحًا واحدًا ضمن نطاق المفاتيح. تعد مجموعات البتات سريعة جدًا، ولا تتطلب سوى الوقت. ^[36] يتعامل نوع Judy1 من مجموعة Judy مع مفاتيح 64 بت بكفاءة. ^[37]${\textstyle O(1)}$

للحصول على نتائج تقريبية، تقوم مرشحات بلوم ، وهي بنية بيانات احتمالية أخرى تعتمد على التجزئة، بتخزين مجموعة من المفاتيح عن طريق ترميز المفاتيح باستخدام مصفوفة بتات ووظائف تجزئة متعددة. تعد مرشحات بلوم أكثر كفاءة في استخدام المساحة من مصفوفات البتات في معظم الحالات وليست أبطأ كثيرًا: مع وظائف التجزئة، تتطلب استعلامات العضوية الوقت فقط. ومع ذلك، تعاني مرشحات بلوم من الإيجابيات الخاطئة . ^{[g] [h] [39]}${\textstyle k}$${\textstyle O(k)}$

توجد هياكل بيانات قد تعمل على تحسين البحث الثنائي في بعض الحالات لكل من عمليات البحث والعمليات الأخرى المتاحة للمصفوفات المرتبة. على سبيل المثال، يمكن إجراء عمليات البحث والمطابقات التقريبية والعمليات المتاحة للمصفوفات المرتبة بكفاءة أكبر من البحث الثنائي على هياكل البيانات المتخصصة مثل أشجار فان إمدي بواس وأشجار الاندماج والمحاولات ومصفوفات البتات . عادةً ما تكون هياكل البيانات المتخصصة هذه أسرع فقط لأنها تستفيد من خصائص المفاتيح ذات السمة المعينة (عادةً المفاتيح التي تكون أعدادًا صحيحة صغيرة)، وبالتالي ستستهلك الوقت أو المساحة للمفاتيح التي تفتقر إلى هذه السمة. ^[22] طالما يمكن ترتيب المفاتيح، يمكن دائمًا إجراء هذه العمليات بكفاءة على الأقل على مصفوفة مرتبة بغض النظر عن المفاتيح. تستخدم بعض الهياكل، مثل مصفوفات جودي، مجموعة من الأساليب للتخفيف من ذلك مع الاحتفاظ بالكفاءة والقدرة على إجراء المطابقة التقريبية. ^[37]

يخزن البحث الثنائي الموحد، بدلاً من الحدود الدنيا والعليا، الفرق في مؤشر العنصر الأوسط من التكرار الحالي إلى التكرار التالي. يتم حساب جدول بحث يحتوي على الاختلافات مسبقًا. على سبيل المثال، إذا كانت المصفوفة المراد البحث فيها هي [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] ، فسيكون العنصر الأوسط ( ) هو 6. في هذه الحالة، يكون العنصر الأوسط للمصفوفة الفرعية اليسرى ( [1, 2, 3, 4, 5] ) هو 3 والعنصر الأوسط للمصفوفة الفرعية اليمنى ( [7, 8, 9, 10, 11] ) هو 9. سيخزن البحث الثنائي الموحد قيمة 3 حيث يختلف كلا المؤشرين عن 6 بنفس المقدار. ^[40] لتقليل مساحة البحث، تضيف الخوارزمية هذا التغيير أو تطرحه من مؤشر العنصر الأوسط. قد يكون البحث الثنائي الموحد أسرع في الأنظمة التي يكون فيها حساب نقطة المنتصف غير فعال، مثل أجهزة الكمبيوتر العشرية . ^[41]${\displaystyle m}$

يمتد البحث الأسّي إلى البحث الثنائي ليشمل القوائم غير المحدودة. ويبدأ بالعثور على أول عنصر بفهرس يكون في نفس الوقت أسًا للرقم اثنين وأكبر من القيمة المستهدفة. وبعد ذلك، يضبط هذا الفهرس كحد أعلى، ويتحول إلى البحث الثنائي. يستغرق البحث تكرارات قبل بدء البحث الثنائي وفي معظم تكرارات البحث الثنائي، حيث هو موضع القيمة المستهدفة. يعمل البحث الأسّي على القوائم المحدودة، ولكنه يصبح تحسنًا على البحث الثنائي فقط إذا كانت القيمة المستهدفة تقع بالقرب من بداية المصفوفة. ^[42]${\textstyle \lfloor \log _{2}x+1\rfloor }$${\textstyle \lfloor \log _{2}x\rfloor }$${\textstyle x}$

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

دالة الاستيفاء الشائعة هي الاستيفاء الخطي . إذا كانت هي المصفوفة، وهما الحدان الأدنى والأعلى على التوالي، و هي الهدف، فإن الهدف يُقدر بأنه على بعد حوالي من و . عند استخدام الاستيفاء الخطي، وتوزيع عناصر المصفوفة موحد أو شبه موحد، فإن بحث الاستيفاء يُجري مقارنات. ^{[43] [44] [45]}${\displaystyle A}$${\displaystyle L,R}$${\displaystyle T}$${\displaystyle (T-A_{L})/(A_{R}-A_{L})}$${\displaystyle L}$${\displaystyle R}$${\textstyle O(\log \log n)}$

في الممارسة العملية، يكون البحث عن طريق الاستيفاء أبطأ من البحث الثنائي للمصفوفات الصغيرة، حيث يتطلب البحث عن طريق الاستيفاء حسابات إضافية. وتنمو تعقيداته الزمنية بشكل أبطأ من البحث الثنائي، ولكن هذا يعوض فقط عن الحسابات الإضافية للمصفوفات الكبيرة. ^[43]

التتابع الكسري هو تقنية تعمل على تسريع عمليات البحث الثنائية لنفس العنصر في عدة مصفوفات مرتبة. يتطلب البحث في كل مصفوفة على حدة وقتًا، حيث هو عدد المصفوفات. يقلل التتابع الكسري هذا إلى تخزين معلومات محددة في كل مصفوفة حول كل عنصر وموقعه في المصفوفات الأخرى. ^{[46] [47]}${\textstyle O(k\log n)}$${\textstyle k}$${\textstyle O(k+\log n)}$

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

تم تعميم البحث الثنائي للعمل على أنواع معينة من الرسوم البيانية، حيث يتم تخزين القيمة المستهدفة في رأس بدلاً من عنصر مصفوفة. أشجار البحث الثنائي هي أحد هذه التعميمات - عندما يتم الاستعلام عن رأس (عقدة) في الشجرة، تتعلم الخوارزمية إما أن الرأس هو الهدف، أو في أي شجرة فرعية سيكون الهدف موجودًا فيها. ومع ذلك، يمكن تعميم ذلك على النحو التالي: نظرًا لوجود رسم بياني غير موجه ومرجح إيجابيًا ورأس مستهدف، تتعلم الخوارزمية عند الاستعلام عن رأس أنه يساوي الهدف، أو يتم منحها حافة واردة تقع على أقصر مسار من الرأس المستعلم عنه إلى الهدف. خوارزمية البحث الثنائي القياسية هي ببساطة الحالة التي يكون فيها الرسم البياني عبارة عن مسار. وبالمثل، فإن أشجار البحث الثنائي هي الحالة التي يتم فيها إعطاء الحواف إلى الأشجار الفرعية اليسرى أو اليمنى عندما تكون الرأس المستعلم عنها غير مساوية للهدف. بالنسبة لجميع الرسوم البيانية غير الموجهة والمرجحة إيجابيا، هناك خوارزمية تجد الرأس المستهدف في الاستعلامات في أسوأ الحالات. ^[48]${\displaystyle O(\log n)}$

تحل خوارزميات البحث الثنائي الصاخبة الحالة التي لا تستطيع فيها الخوارزمية مقارنة عناصر المصفوفة بشكل موثوق. لكل زوج من العناصر، هناك احتمال معين بأن تقوم الخوارزمية بالمقارنة الخاطئة. يمكن للبحث الثنائي الصاخب العثور على الموضع الصحيح للهدف باحتمالية معينة تتحكم في موثوقية الموضع الناتج. يجب على كل إجراء بحث ثنائي صاخب إجراء مقارنات على الأقل في المتوسط، حيث هي دالة إنتروبيا الثنائية و هي احتمال أن ينتج الإجراء الموضع الخاطئ. ^{[49] [50] [51]} يمكن اعتبار مشكلة البحث الثنائي الصاخب حالة من لعبة ريني-أولام ، ^[52] أحد أشكال لعبة العشرين سؤالاً حيث قد تكون الإجابات خاطئة. ^[53]${\displaystyle (1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}}$${\displaystyle H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)}$${\displaystyle \tau }$

تقتصر أجهزة الكمبيوتر الكلاسيكية على أسوأ حالة من التكرارات الدقيقة عند إجراء بحث ثنائي. لا تزال الخوارزميات الكمومية للبحث الثنائي مقيدة بنسبة من الاستعلامات (تمثل تكرارات الإجراء الكلاسيكي)، ولكن العامل الثابت أقل من واحد، مما يوفر تعقيدًا زمنيًا أقل على أجهزة الكمبيوتر الكمومية . أي إجراء بحث ثنائي كمي دقيق - أي إجراء يعطي دائمًا النتيجة الصحيحة - يتطلب استعلامات على الأقل في أسوأ الحالات، حيث هو اللوغاريتم الطبيعي . ^[54] يوجد إجراء بحث ثنائي كمي دقيق يعمل في الاستعلامات في أسوأ الحالات. ^[55] بالمقارنة، تعد خوارزمية جروفر هي الخوارزمية الكمومية المثلى للبحث في قائمة غير مرتبة من العناصر، وتتطلب استعلامات. ^[56]${\textstyle \lfloor \log _{2}n+1\rfloor }$${\textstyle \log _{2}n}$${\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}$${\textstyle \ln }$${\textstyle 4\log _{605}n\approx 0.433\log _{2}n}$${\displaystyle O({\sqrt {n}})}$

تعود فكرة فرز قائمة العناصر للسماح بالبحث بشكل أسرع إلى العصور القديمة. كان أقدم مثال معروف هو لوح Inakibit-Anu من بابل الذي يعود تاريخه إلى حوالي 200  قبل الميلاد . احتوى اللوح على حوالي 500 رقم ستيني ومقلوباتها مرتبة حسب الترتيب المعجمي ، مما جعل البحث عن إدخال معين أسهل . بالإضافة إلى ذلك، تم اكتشاف العديد من قوائم الأسماء التي تم فرزها حسب الحرف الأول منها في جزر بحر إيجه . كان Catholicon ، وهو قاموس لاتيني انتهى في عام 1286 م، أول عمل يصف قواعد فرز الكلمات حسب الترتيب الأبجدي، بدلاً من الأحرف القليلة الأولى فقط. ^[9]

في عام 1946، ذكر جون ماوتشلي لأول مرة البحث الثنائي كجزء من محاضرات مدرسة مور ، وهي دورة جامعية أساسية في الحوسبة. ^[9] في عام 1957، نشر ويليام ويسلي بيترسون أول طريقة للبحث الاستيفاء. ^{[9] [57]} عملت كل خوارزمية بحث ثنائي منشورة فقط على المصفوفات التي يقل طولها عن قوة اثنين بمقدار واحد ^[i] حتى عام 1960، عندما نشر ديريك هنري ليهمر خوارزمية بحث ثنائي تعمل على جميع المصفوفات. ^[59] في عام 1962، قدم هيرمان بوتينبروخ تنفيذًا للبحث الثنائي ALGOL 60 الذي وضع المقارنة للمساواة في النهاية، مما زاد متوسط ​​عدد التكرارات بمقدار واحد، ولكن قلل إلى واحد عدد المقارنات لكل تكرار. ^[8] تم تطوير البحث الثنائي الموحد بواسطة AK Chandra من جامعة ستانفورد في عام 1971. ^[9] في عام 1986، قدم برنارد شازيل وليونيداس جيه. جيباس التتابع الكسري كطريقة لحل العديد من مشاكل البحث في الهندسة الحسابية . ^{[46] [60] [61]}

على الرغم من أن الفكرة الأساسية للبحث الثنائي واضحة نسبيًا، إلا أن التفاصيل قد تكون صعبة بشكل مدهش

—  دونالد كنوث ^[2]

عندما عيّن جون بنتلي البحث الثنائي كمشكلة في دورة للمبرمجين المحترفين، وجد أن تسعين بالمائة فشلوا في تقديم حل صحيح بعد عدة ساعات من العمل عليه، ويرجع ذلك أساسًا إلى فشل التنفيذات غير الصحيحة في التشغيل أو إرجاع إجابة خاطئة في حالات نادرة . ^[62] تُظهر دراسة نُشرت عام 1988 أن الكود الدقيق لها موجود فقط في خمسة من أصل عشرين كتابًا مدرسيًا. ^[63] علاوة على ذلك، احتوى تنفيذ بنتلي الخاص للبحث الثنائي، الذي نُشر في كتابه Programming Pearls عام 1986 ، على خطأ فيض ظل غير مكتشف لأكثر من عشرين عامًا. كان تنفيذ مكتبة لغة برمجة جافا للبحث الثنائي يعاني من نفس خطأ الفيض لأكثر من تسع سنوات. ^[64]

في التنفيذ العملي، غالبًا ما تكون المتغيرات المستخدمة لتمثيل المؤشرات ذات حجم ثابت (أعداد صحيحة)، وقد يؤدي هذا إلى تجاوز فيض حسابي للمصفوفات الكبيرة جدًا. إذا تم حساب نقطة المنتصف للنطاق على أنها ، فقد تتجاوز قيمة نطاق الأعداد الصحيحة لنوع البيانات المستخدم لتخزين نقطة المنتصف، حتى إذا كانت و ضمن النطاق. إذا كانت و غير سالبة، فيمكن تجنب ذلك عن طريق حساب نقطة المنتصف على أنها . ^[65]${\displaystyle {\frac {L+R}{2}}}$${\displaystyle L+R}$${\displaystyle L}$${\displaystyle R}$${\displaystyle L}$${\displaystyle R}$${\displaystyle L+{\frac {R-L}{2}}}$

قد تحدث حلقة لا نهائية إذا لم يتم تعريف شروط الخروج للحلقة بشكل صحيح. بمجرد تجاوز ، فإن البحث قد فشل ويجب أن ينقل فشل البحث. بالإضافة إلى ذلك، يجب الخروج من الحلقة عند العثور على العنصر المستهدف، أو في حالة التنفيذ حيث يتم نقل هذا الفحص إلى النهاية، يجب أن تكون عمليات التحقق مما إذا كان البحث ناجحًا أو فاشلاً في النهاية موجودة. وجد بنتلي أن معظم المبرمجين الذين نفذوا البحث الثنائي بشكل غير صحيح ارتكبوا خطأ في تحديد شروط الخروج. ^{[8] [66]}${\displaystyle L}$${\displaystyle R}$

تتضمن مكتبات العديد من اللغات القياسية إجراءات بحث ثنائية:

• توفر لغة C الوظيفة bsearch() في مكتبتها القياسية ، والتي يتم تنفيذها عادةً عبر البحث الثنائي، على الرغم من أن المعيار الرسمي لا يتطلب ذلك. ^[67]
• توفر مكتبة C++ القياسية الوظائف binary_search()، lower_bound()، upper_bound()و equal_range(). ^[68]
• توفر مكتبة Phobos القياسية في لغة Dstd.range ، في الوحدة النمطية، نوعًا SortedRange(يتم إرجاعه بواسطة الوظائف sort()و assumeSorted()) مع الطرق contains()و equaleRange()و lowerBound()و trisect()التي تستخدم تقنيات البحث الثنائي بشكل افتراضي للنطاقات التي توفر وصولاً عشوائيًا. ^[69]
• توفر لغة COBOLSEARCH ALL الفعل لإجراء عمليات بحث ثنائية على جداول مرتبة بلغة COBOL. ^[70]
• تحتوي حزمة مكتبة Go القياسية sortعلى الوظائف Search، SearchInts، SearchFloat64s، و SearchStrings، والتي تنفذ البحث الثنائي العام، بالإضافة إلى تنفيذات محددة للبحث في شرائح الأعداد الصحيحة، والأعداد ذات الفاصلة العائمة، والسلاسل، على التوالي. ^[71]
• توفر Java مجموعة من الطرق الثابتة المحملة binarySearch() في الفئات Arraysوفي الحزمة Collectionsالقياسية java.utilلإجراء عمليات بحث ثنائية على مصفوفات Java وعلى Lists على التوالي. ^{[72] [73]}
• يقدم إطار عمل Microsoft .NET Framework 2.0 إصدارات عامة ثابتة من خوارزمية البحث الثنائي في فئات قاعدة المجموعة الخاصة به. ومن الأمثلة على ذلك System.Arrayطريقة BinarySearch<T>(T[] array, T value). ^[74]
• بالنسبة لـ Objective-C ، يوفر إطار عمل CocoaNSArray -indexOfObject:inSortedRange:options:usingComparator: الطريقة في Mac OS X 10.6+. ^{[75] يحتوي إطار عمل} Core Foundation C الخاص بشركة Apple أيضًا على CFArrayBSearchValues()وظيفة. ^[76]
• يوفر بايثونbisect الوحدة التي تحافظ على القائمة مرتبة دون الحاجة إلى فرز القائمة بعد كل إدراج. ^[77]
• تتضمن فئة Array في Rubybsearch طريقة ذات مطابقة تقريبية مدمجة. ^[78]
• توفر شريحة Rustbinary_search() البدائية ، binary_search_by()، binary_search_by_key()، و partition_point(). ^[79]

• طريقة التقسيم الثنائي  – خوارزمية لإيجاد صفر الدالة – ​​نفس الفكرة المستخدمة لحل المعادلات في الأعداد الحقيقية
• البحث الثنائي المضاعف  – تباين البحث الثنائي مع حساب نقطة المنتصف المبسطة

تم تقديم هذه المقالة إلى WikiJournal of Science للمراجعة الأكاديمية الخارجية في عام 2018 (تقارير المراجعين). تمت إعادة دمج المحتوى المحدث في صفحة ويكيبيديا بموجب ترخيص CC-BY-SA-3.0 ( 2019 ). إصدار السجل كما تمت مراجعته هو: Anthony Lin؛ et al. (2 يوليو 2019). "خوارزمية البحث الثنائي" (PDF) . WikiJournal of Science . 2 (1): 5. doi : 10.15347/WJS/2019.005 . ISSN  2470-6345. Wikidata  Q81434400.

• قاموس NIST للخوارزميات وهياكل البيانات: البحث الثنائي
• مقارنات ومعايير لمجموعة متنوعة من تطبيقات البحث الثنائي في لغة C أرشيف 25 سبتمبر 2019 على موقع Wayback Machine