بحث اثناني: الفرق بين النسختين

بيانات عامّة
الصنف	خوارزمية بحث
بنية البيانات	مصفوفة
أسوء حالة	O(log n)
الحالة المُثلى	O(1)
الأداء الوسطي	O(log n)
أسوأ حالة تعقيد مكاني	O(1)

→ التعديل السابق

مرئينص الويكي

النسخة الحالية 09:54، 11 يونيو 2026

في علم الحاسوب، البحث الاثناني^{[عر 1]} خوارزمية بحث تجد موضع القيمة المستهدَفة داخل مصفوفة مُرتَّبة.^[1] يقارن البحث الاثناني القيمة المستهدفة بقيمة العنصر في منتصف المصفوفة. إذا تتساوى القيمتان، يُستبعَد النصف الذي لا يمكن للهدف أن يكون فيه ويستمر البحث في النصف الآخر؛ تُكرَّر العملية مرة أخرى مع أخذ العنصر المتوسط للمقارنة بالقيمة المستهدَفة، حتى العثور عليها. إذا خَلُص البحث إلى أن النصف الآخر فارغ، أي لا عناصر فيه، فهذا يعني أن القيمة المُستهدَفة غير موجودة في المصفوفة أصلًا.

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

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

التسمية

يُسمَّى البحث الاثناني أيضًا بالعربية: البحث الثنائي^{[عر 2]} أو خوارزمية البحث الثنائي^{[عر 3]} (الإنجليزية: Binary search أو Binary search algorithm) أو البحث بالتنصيف^{[عر 3]} ، ومن أسمائه المترجمة من الإنجليزية: البحث المُحدَّد بفاصل المنتصف،^[3] والبحث اللغارتمي،^[4] والقطع الاثناني.^[5]^[أ]

خوارزمية العمل

الإجرائيات

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

الإجرائية الرئيسة

إذا كانت $A$ مصفوفةً تحتوي على $n$ عنصر أو سجل هي: $A_{0}, A_{1}, A_{2}, \dots, A_{n - 1}$ مرتبة بالشكل التالي: $A_{0} \leq A_{1} \leq A_{2} \leq \dots \leq A_{n - 1}$ ، وإذا كانت القيمة المُستهدَفة هي $T$ ، فبالإمكان العثور على مرتبة القيمة المستهدفة $T$ في المصفوفة $A$ ، أي إنجاز بحثٍ اثناني، باستخدم الخوارزمية التالية:^[4]

$L$ و $R$ مُتغيِّران،^[ب] اضبط قيمة $L$ إلى $0$ وقيمة $R$ إلى $n - 1$ .
إذا كانت المُتراجِحة $L > R$ ، البحث غير ناجح، نهاية.
$m$ مُتغيِّر يُمثِّل قيمة موقع العنصر المتوسط، اضبط قيمته إلى قيمة الجزء الصحيح المَحسُوب بالعلاقة $\frac{L + R}{2}$ ، أي أن $m$ هو أكبر عدد صحيح أصغر أو يساوي القيمة $\frac{L + R}{2}$ .
Am<T مُتغيِّر يُمثِّل قيمة العنصر الذي مرتبته m في المصفوفة A:
1. إذا كانت المُتراجِحة $A_{m} < T$ مُحققة، اضبط قيمة $L$ إلى $m + 1$ ، ثُمَّ انتقل إلى الخطوة 2.
2. إذا كانت المتراجحة $A_{m} > T$ مُحققة، اضبط قيمة $R$ إلى $m - 1$ ، ثُمَّّ انتقل إلى الخطوة 2.
3. وإلا، فإنَّ المساواة $A_{m} = T$ محققة، أرجع قيمة $m$ ، نهاية.

تتبع هذه الإجرائية التكرارية حدود البحث باستخدام المتغيرين $L$ و $R$ اللّذين يُمثِّلان دائماً الحدين الأسفل والأعلى على الترتيب لجزء المصفوفة الذي تُطبَّق خوارزمية البحث الاثناني عليه. يمكن أيضاً التعبير عن الخوارزمية السابقة بشبه الرماز التالي، وفيه تبقى أسماء المتغيرات وأنواعها كما هي أعلاه، ويُمثِّل floor دالة أرضية، وتشير الكلمة unsuccessful إلى قيمة رقمية محددة تُعبِّر عن إخفاق البحث.^[4]

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m - 1
        else:
            return m
    return unsuccessful

يمكن أيضاً أن تُستبدل الدالة السقفية ceil بالدالة الأرضية المستخدمة على القيمة $\frac{L + R}{2}$ . ولكن هذا قد يؤدي إلى إعطاء نتيجة مُغايرة إذا وجدت القيمة المُستهدَفة أكثر من مرة في المصفوفة.

إجرائية بديلة

ينجح البحث في الإجرائية الرئيسة إذا كانت قيمة العنصر المتوسط $m$ تساوي القيمة المُستهدَفة ( $T$ ) في كل تكرار. تتخلى بعض تنفيذات الخوارزمية عن إجراء هذا الفحص أثناء كل تكرار، ولا تنفّذه إلا عند بقاء عنصر واحد فقط، أي عندما يكون $L = R$ . ينتج عن هذا التغيير حلقة مقارنة أسرع بسبب استبعاد إجراء عملية المقارنة مرةً واحدةً عند كل تكرار. ولكن هذه الطريقة تتطلب إجراء تكرارٍ إضافي واحد في المتوسط.^[6]

نشر هيرمان بوتينبروش أول تنفيذ للخوارزمية يتخلى عن إجرائية فحص المساواة بالشكل السابق في عام 1962م.^[6]^[7]

اضبط قيمة $L$ إلى $0$ وقيمة $R$ إلى $n - 1$ .
طالما ما يزال الشرط L≠R مُتحققاً:
1. اضبط قيمة $m$ إلى قيمة المتمم الصحيح الأعلى المحسوب بالعلاقة $\frac{L + R}{2}$ ، وهو أصغر عدد صحيح يكون أكبر أو يساوي القيمة $\frac{L + R}{2}$ .
2. إذا كانت المتراجحة $A_{m} > T$ متحققة، اضبط قيمة $R$ إلى $m - 1$ .
3. وإلا، أي عندما يتحقق $A_{m} \leq T$ ، اضبط قيمة $L$ إلى $m$ .
الآن، افحص المساواة $L = R$ ، إذا كان الشرط $A_{L} = T$ متحققاً، أَرجِع $L$ ، نهاية. وإلا، بحث غير ناجح، نهاية.

يمكن أيضاً التعبير عن الخوارزمية السابقة بشبه الرماز التالي:

    function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m - 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

التعامل مع العناصر المكررة

قد تُرجِع الإجرائية مرتبة أي عنصر تكون قيمته مساويةً للقيمة المستهدفة، حتى ولو كان هناك عناصر مُكرَرة في المصفوفة. على سبيل المثال، إذا كانت المصفوفة التي يُراد البحث فيها هي: $[1, 2, 3, 4, 4, 5, 6, 7]$ وكانت القيمة المستهدفة هي $4$ ، فإن الخوارزمية سُترجع العنصر الرابع، أي الذي تكون قيمة مرتبته 3، والخامس، أي الذي تكون قيمة مرتبته 4. ستعيد إجرائية الرئيسة العنصر الرابع فقط في هذه الحالة. في بعض الأحيان، يكون من الضروري العثور على موقع العنصر الموجود في أقصى اليسار أو العنصر الموجود في أقصى اليمين ضمن مجموعة العناصر المكررة في المصفوفة. في المثال أعلاه، ومن أجل العناصر المكررة التي تكون قيمتها 4، فإنَّ العنصر الرابع هو العنصر الموجود في أقصى اليسار، في حين أن العنصر الخامس هو العنصر الموجود في أقصى اليمين. في الإجرائية البديلة، إذا وجدت مجموعة من العناصر المكررة، فإن مرتبة العنصر الموجود في أقصى اليمين سيعاد دائماً.^[7]

إجرائية لإرجاع العنصر الموجود في أقصى اليسار

إذا كانت المصفوفة المُرتبة تحتوي على مجموعة من العناصر مكررة عددها $n$ ، يمكن استعمال الخوارزمية التالية لإرجاع العنصر الموجود في أقصى يسار مجموعة العناصر المرتبة:^[8]

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

إذا كانت المتراجحة $L < n$ والشرط $A_{L} = T$ مُحققان، فإن $A_{L}$ هو العنصر الموجود في أقصى يسار مجموعة العناصر التي تساوي قيمة كل منها القيمة المستهدفة $T$ . حتى وإن كانت القيمة المستهدفة غير موجودة في المصفوفة، فإن قيمة $L$ ، الناتجة عن تنفيذ الإجرائية، ستمثل مرتبة القيمة المستهدفة التي يجب أن تكون فيها، لو وجدت في المصفوفة، أو عدد عناصر المصفوفة التي كانت ستوجد قبل العنصر المُحدد بالقيمة المستهدفة.

يمكن أيضاً التعبير عن الخوارزمية السابقة بشبه الرماز التالي:

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

إجرائية لإرجاع العنصر الموجود في أقصى اليمين

إذا كانت المصفوفة المُرتبة تحتوي على مجموعة متكررة من العناصر عددها $n$ ، يمكن استعمال الخوارزمية التالية لإرجاع العنصر الموجود في أقصى يمين مجموعة العناصر المرتبة:^[8]

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

إذا كانت المتراجحة $L > 0$ والشرط $A_{L - 1} = T$ مُتحققان، فإن $A_{L - 1}$ هو العنصر الموجود في أقصى يمين مجموعة العناصر التي تساوي قيمة كل منها القيمة المستهدفة $T$ . حتى وإن كانت القيمة المستهدفة غير موجودة في المصفوفة، فإن قيمة $n - L$ ، الناتجة عن تنفيذ الإجرائية، ستمثِّل عدد عناصر المصفوفة التي كانت ستوجد بعد العنصر المُحدد بالقيمة المستهدفة، لو وُجِدَ.

يمكن أيضاً التعبير عن الخوارزمية السابقة ببشبه الرماز التالي:

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

تطابقات تقريبية

ملف:Approximate-binary-search-ar.svg

يمكن تكييف البحث الاثناني لحساب التطابقات التقريبية. في المثال أعلاه، تعرض المرتبتان السابقة واللاحقة وأقرب جار للقيمة المستهدفة

5

، وهي قيمة غير موجودة في المصفوفة.

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

يمكن أيضاً تنفيذ استعلامات عن المرتبة بالإجرائية الخاصة بالعثور على العنصر الموجود في أقصى اليسار، حيث يُرجع عدد العناصر التي تكون قيمتها أقل من القيمة المستهدفة.^[9] ويمكن تنفيذ استعلامات عن المرتبة السابقة باستخدام الاستعلامات عن المرتبة، فإذا كانت مرتبة القيمة المستهدَفة $r$ ، فإن مرتبة القيمة السابقة هي $r - 1$ .^[10] أما فيما يخص استعلامات مرتبة القيمة اللاحقة، فبالإمكان استخدام الإجرائية المُخصصة للعثور على العنصر الموجود في أقصى اليمين لأجل ذلك، فإذا كانت نتيجة مرتبة القيمة المستهدفة هي $r$ ، فإن مرتبة القيمة اللاحقة لها هي $r + 1$ .^[10] يُحدد الجار الأقرب للقيمة المستهدفة بالنظر إلى المرتبتين السابقة واللاحقة لها، واختيار أقرب منهما. تٌنفَّذ الاستعلامات عن النطاق حسبَ ما يأتي: قي البداية تُحدد مرتبتي القيمتين، ثُمَّ يُحسَب عدد العناصر ذات القيمة المساوية أو الأكبر من الأولى والأقل من القيمة الثانية بإيجاد الفرق بين المرتبتين.^[10] يمكن تعديل هذا العدد نحو القيمة الصحيحة التالية أو السابقة، أي التي تنقص أو تزيد بمقدار واحد، حسبَ طريقة تحديد بداية ونهاية النطاق، أي هل نقطة البداية ونقطة النهاية جزءٌ من النطاق أم لا، وهل تحتوي المصفوفة على عناصر تتطابق قيمتها مع نقاط النهاية أم لا.^[11]

تقييم الأداء

ملف:Binary search example tree.svg

شجرة اثنانية تُمثِّل عملية البحث الاثناني. المصفوفة التي يطبق الإجراء عليها هي

[20, 30, 40, 50, 80, 90, 100]

، والقيمة المستهدفة هي

40

.

ملف:Binary search complexity-ar.svg

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

يمكن تحليل أداء البحث الاثناني باستعرض سير الإجراء على شجرة اثنانية ومراقبة عدد المقارنات. تكون العقدة الجذر في الشجرة هي العنصر المتوسط في المصفوفة. بعد ذلك، يكون العنصر المتوسط في النصف الأسفل من المصفوفة هو العقدة الفرعية اليسرى للجذر، والعنصر المتوسط في النصف الأعلى من المصفوفة هو العقدة الفرعية اليمنى للجذر. ثمَّ يُبنى ما تبقى من الشجرة الاثنانية باتباع نفس الطريقة. عند تطبيق الإجراء، يبدَأ البحث من العقدة الجذر، وتكون هي العقدة المنظورة، وتقارن قيمتها مع القيمة المُستهدفة، فإذا كانت القيمة المُستهدَفة أكبر من قيمة العقدة المنظورة تصبح العقدة المنظورة التالية هي العقدة الفرعية اليمنى للجذر، وإذا كانت القيمة المُستهدفة أصغر من قيمة العقدة المنظورة فإن العقدة المنظورة التالية تصبح العقدة الفرعية اليسرى للجذر، وتكرر عملية المقالة والتحرك على فروع الشجرة الاثنانية نحو اليمين أو اليسار حسبَ ما سبق، حتى تكون القيمة المُستهدفة مساوية للقيمة المنظورة، وعندها البحث يتوقف بنجاح.^[2]^[12]

يكرر البحث الاثناني حلقة المقارنة $⌊ \log_{2} (n) + 1 ⌋$ مرَّة في أسوأ حالة، وفيها $⌊ ⌋$ هو تمثيل الدالة الأرضية، وتعطي أكبر عدد صحيح يكون أصغر أو مساوٍ للقيمة التي تمرر لها، أي إذا مررنا 2.5 مثلاً، فإنها ستعيد القيمة 2. أمَّا $\log_{2}$ فهي دالة اللغارتم الاثناني. ويعني الوصول إلى الحالة الأكثر سوءاً بلوغ أعمق مستوى للشجرة. في شجرة بحث اثناني عدد عناصرها $n$ هناك دائماً $⌊ \log_{2} (n) + 1 ⌋$ مستوىً. ويمكن أيضاً الوصول إلى الحالة الأكثر سوءاً عندما تكون القيمة المستهدفة غير موجودة في المصفوفة.^[13]

يُحسب متوسط عدد مرات تكرار إجراء البحث الاثناني مع افتراض البحث عن كل عنصر موجود في المصفوفة بالعلاقة التالية:

⌊ \log_{2} (n) ⌋ + 1 - (2^{⌊ \log_{2} (n) ⌋ + 1} - ⌊ \log_{2} (n) ⌋ - 2) / n

ويساوي تقريباً $\log_{2} (n) - 1$ تكرارًا.

إذا لم تكن القيمة المستهدفة في المصفوفة، فإن عدد مرات تكرار الإجراء يُحسب وسطياً بالعلاقة:

⌊ \log_{2} (n) ⌋ + 2 - 2^{⌊ \log_{2} (n) ⌋ + 1} / (n + 1)

وذلك على افتراض البحث عن كل عنصر موجود في المصفوفة.^[12]

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

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

تعقيد الفضاء

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

اشتقاق الحالة المتوسطة

يعتمد متوسط عدد التكرارات التي يُنجزها البحث الاثناني على احتمال وجود كل عنصر يجري البحث عنه. تختلف الحالة المتوسطة لعمليات البحث الناجحة عن تلك المرتبطة بعمليات البحث غير الناجحة. تُعرَّف الحالة المتوسطة لعمليات البحث الناجحة بأنها عدد التكرارات المطلوبة للبحث في كل عنصر في المصفوفة مرة واحدة بالضبط، مقسومةً على عدد العناصر $n$ فيها. أما الحالة المتوسطة لعمليات البحث غير الناجحة فهي عدد التكرارات المطلوبة للبحث عن عنصر ما في كل المجالات الفاصلة مرة واحدة بالضبط، مَقسُوماً على عدد الفواصل، أي $n + 1$ .^[12]

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

عمليات البحث الناجحة

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

بما أن خوارزمية البحث الاثناني هي الخوارزمية المثلى لعمليات البحث مع مقارنة، فإن بالإمكان اختزال هذه المسالة لحساب الطول الأصغر للمسار الداخلي في الأشجار الاثنانية التي تضم $n$ عقدة، أي إلى $I (n)$ ، وهو يُحسب باستعمال العلاقة:^[16]

I (n) = \sum_{k = 1}^{n} ⌊ \log_{2} (k) ⌋

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

\sum_{k = 1}^{7} ⌊ \log_{2} (k) ⌋ = 0 + 2 (1) + 4 (2) = 2 + 8 = 10

أمَّا متوسط عدد التكرارات فيمكن أن يحسب وفق معادلة الحالة المتوسطة وتكون قيمته: $1 + \frac{10}{7} = 2 \frac{3}{7}$ .

ويمكن أيضاً تبسيط طول المسارات الداخلية $I (n)$ أيضاً وفق ما يأتي:^[12]

I (n) = \sum_{k = 1}^{n} ⌊ \log_{2} (k) ⌋ = (n + 1) ⌊ \log_{2} (n + 1) ⌋ - 2^{⌊ \log_{2} (n + 1) ⌋ + 1} + 2

وإذا عُوِّضت القيمة السابقة لطول المسارات الداخلية في معادلة حساب متوسط عدد التكرارات لعملية بحث ناجحة، أي $I (n)$ ، فإنها تؤول إلى الشكل التالي:^[12]

T (n) = 1 + \frac{(n + 1) ⌊ \log_{2} (n + 1) ⌋ - 2^{⌊ \log_{2} (n + 1) ⌋ + 1} + 2}{n} = ⌊ \log_{2} (n) ⌋ + 1 - (2^{⌊ \log_{2} (n) ⌋ + 1} - ⌊ \log_{2} (n) ⌋ - 2) / n

من أجل عدد صحيح ما $n$ ، فإن هذه العلاقة تكافئ تلك المُستعملة لحساب الحالة المتوسطة في بحث ناجح.

عمليات البحث غير الناجحة

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

يُعرَّف المسار الخارجي بأنه مسارٌ يبدأ من الجذر وينتهي في عقدة خارجية، وطول المسار الخارجي نحو عنصر ما بأنه عدد الوصلات فيه، وطول المسار الخارجي هو مجموع أطوال المسارات الخارجية نحو عناصر المصفوفة جميعها.

إذا وُجِد $n$ عنصر في المصفوفة، وهو عدد صحيح موجب، وإذا كان طول المسار الخارجي هو $E (n)$ ، فإنَّ متوسط عدد التكرارات لعملية بحث غير ناجح يحسب بالعلاقة التالية:

T^{'} (n) = \frac{E (n)}{n + 1}

قُسِّم طول المسار الخارجي على $n + 1$ بدلًا من $n$ لأن هناك $n + 1$ مساراً خارجياً، يمثل الفواصل بين عناصر المصفوفة نفسهم وبين عناصر المصفوفة والعناصر الخارجية.^[12]

وبنفس الطريقة المتبعة مع عمليات البحث الناجحة، يمكن اختزال هذه المسألة لتحديد الطول الأدنى للمسار الخارجي لجميع الأشجار الاثنانية من أجل $n$ عقدة وهو يساوي طول المسار الداخلي مضافاً له $2 n$ .^[16] وبتعويض ذلك في المعادلة المستخدمة لحساب طول المسارات الداخلية $I (n)$ تنتج المعادلة التالية لحساب طول المسار الخارجي:^[12]

E (n) = I (n) + 2 n = [(n + 1) ⌊ \log_{2} (n + 1) ⌋ - 2^{⌊ \log_{2} (n + 1) ⌋ + 1} + 2] + 2 n = (n + 1) (⌊ \log_{2} (n) ⌋ + 2) - 2^{⌊ \log_{2} (n) ⌋ + 1}

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

T^{'} (n) = \frac{(n + 1) (⌊ \log_{2} (n) ⌋ + 2) - 2^{⌊ \log_{2} (n) ⌋ + 1}}{(n + 1)} = ⌊ \log_{2} (n) ⌋ + 2 - 2^{⌊ \log_{2} (n) ⌋ + 1} / (n + 1)

تقييم أداء الإجراء البديل

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

ثمة شكل من أشكال خوارزمية البحث الاثناني يتحقق فيما إذا كان العنصر المتوسط يساوي الهدف في نهاية البحث فقط. وسطياً، يلغي هذا الشكل نصف مقارنة من كل تكرار. يؤدي هذا إلى تقليل الوقت المستغرق في التكرار بشكل طفيف على معظم أجهزة الحاسوب. وتضمن هذه الخوارزمية مع ذلك أن يُنجز البحث بالعدد الأقصى من التكرارات. يضاف تكرارٌ واحد وسطياً إلى البحث، بسبب تنفيذ حلقة المقارنة $⌊ \log_{2} (n) + 1 ⌋$ مرة فقط في أسوأ الحالات. إن الزيادة الطفيفة في قيمة الكفاءة من أجل كل تكرار لا تعوّض التكرار الفائض الإجمالي في كل الحالات، بل فقط عندما يكون عدد العناصر $n$ كبيراً جداً.^[17]^[18]^[د]

وقت التشغيل واستخدام ذاكرة التخزين المؤقت

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

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

مقارنة مع طرق بحث أخرى

إن استعمال المصفوفات المرتبة مع البحث اثناني حلٌ غير فعال عندما تكون عمليات الإدراج والحذف في المصفوفة متداخلة مع الاسترجاع، ويستغرق ذلك زمناً هو $O (n)$ لكل عملية من هذا القبيل. بالإضافة إلى ذلك، يمكن أن تؤدي المصفوفات التي المُرتَّبة إلى تعقيد استخدام الذاكرة خاصة عندما تحصل عملية إدراج العناصر في المصفوفة بشكل متكرر.^[20] ثمة بنى بيانات أخرى تدعم الإدراج والحذف بشكل أكثر كفاءة.

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

بحث خطي

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

الأشجار

ملف:Binary search tree search 4.svg

يُنجر البحث في أشجار البحث الاثناني باستخدام خوارزمية مشابهة للبحث الاثناني.

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

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

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

التلبيد

جداول التلبيد بنية بيانات تَقرُن كل سجل بمفتاح فريد يُحسب باستخدام دلة التلبيد. عند تنفيذ المصفوفات الترابطية، تكون جداول التلبيد عموماً أسرع من البحث الاثناني في مصفوفة سجلات مرتبة.^[30] تتطلب معظم تطبيقات جدول التجزئة زمناً ثابتاً مستهلكاً في المتوسط.^[31]^[ز] ومع ذلك، ليس التلبيد ذو فائدة لإيجاد التطابقات التقريبية، مثل حساب المفتاح التالي الأصغر التالي والمفتاح الأكبر التالي والمفتاح الأقرب، والمعلومة الوحيدة المستخلصة من بحثٍ غير ناجح هي أن القيمة المُستهدَفة غير مقترنة مع أي سجل. البحث الاثناني مثاليٌ لمثل هذه التطابُقات لأنه ينجزها في وقت لغارتمي.^[21]

خوارزميات تعيين العضوية

خوارزميات تعيين العضوية مرتبطة بعملية البحث، ويمكن استخدام أي خوارزمية بحث، مثل البحث الاثناني، من أجل تعيين العضوية أيضاً. ثمة خوارزميات أخرى أكثر ملاءمة للعضوية المُحدَّدة، فمصفوفة البت مثلاً هي الأبسط والأكثر إفادة عندما يكون نطاق المفاتيح محدوداً، وهي تُخزِّن مجموعة من البتات المضغوطة التي يُمثِّل كل منها مفتاحاً واحداً في نطاق المفاتيح. هذه المصفوفات سريعة للغاية أيضاً، وتتطلب زمناً هو $O (1)$ فقط.^[33] يعالج النوع الأول من مصفوفة جودي مفاتيح بطول 64 بت بكفاءة.

تُخزِّن مرشحات بلوم، وهي بنية بيانات احتمالية أخرى تستند إلى التلبيد مجموعة من المفاتيح عن طريق ترميزها باستخدام مصفوفة بت ودوال تلبيد متعددة للحصول على نتائج تقريبية. مُرشِّحات بلوم أكثر فعالية بالنسبة لمساحة التخزين مقارنة مع مصفوفات البت في معظم الحالات وليست أبطأ منها بكثير: حيث يستغرق إنجاز $k$ دالة تجزئة من أجل استعلامات العضوية زمناً هو $O (k)$ فقط. ولكن مُرشِّحات بلوم تعاني من الأخطاء الإيجابية.^[34]^[ح]^[ط]

بنى بيانات أخرى

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

اختلافات

البحث الاثناني المنتظم

ملف:Uniform binary search-ar.svg

يُخزِّن البحث الاثناني الموحَّد الفرق بين العنصر الحالي والعنصرين المتوسطين المحتملين التاليين بدلاً من الحدود المحددة.

يُخزِّن البحث الاثناني المنتظم الفرق بين فهرسي العنصر المتوسط في تكرارين متتابعين، بدلاً من الحدين الأسفل والأعلى، ويُحسب مسبقاً جدول بحث يضم هذه الفروق سلفاً. على سبيل المثال، إذا كانت المصفوفة المراد البحث فيها هي: $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]$ ، فإن العنصر المتوسط ( $m$ ) سيكون $6$ . في هذه الحالة، يكون العنصر المتوسط من المصفوفة الفرعية اليسرى ( $[1, 2, 3, 4, 5]$ ) هو 3 والعنصر المتوسط من المصفوفة الفرعية اليمنى ( $[7, 8, 9, 10, 11]$ ) هو $9$ . سيُخزِّن البحث الاثناني المنتظم القيمة 3 حيث يبتعد كلا المؤشرين عن 6 بنفس المقدار.^[36] لتقليل فضاء البحث، تضيف الخوارزمية التغيير السابق أو تطرحه من فهرس العنصر المتوسط. قد يكون البحث الاثناني الموحَّد أسرع في الأنظمة التي يكون حساب نقطة المنتصف غير فعالٍ، مثل أجهزة الحاسوب العشرية.^[37]

البحث الأسي

ملف:Exponential search-ar.svg

يصور البحث الأسي إيجاد الحد الأعلى للبحث الاثناني اللاحق.

يوسِّع البحثُ الأسي البحثَ الاثناني ليشمل القوائم غير المحدودة. يبدأ البحث الأسي بالعثور على أول عنصر يكون مُؤَشِّره من مضاعفات العدد 2 وأكبر من القيمة المستهدفة. بعد ذلك، يُضبط هذا الفهرس ليكون حداً أعلى، ثمَّ يُطبَّق البحث الاثناني. يستغرق البحث $⌊ \log_{2} x + 1 ⌋$ تكراراً قبل بدء البحث الاثناني و $⌊ \log_{2} x ⌋$ تكراراً على الأكثر بعد بدء البحث الاثناني، حيث $x$ هو فهرس القيمة المستهدفة. يعمل البحث الأسي على القوائم المقيدة أيضاً، ولكنه يصبح تحسيناً للبحث الاثناني فقط في الحالة التي تكون فيها القيمة المستهدفة قريبة من بداية المصفوفة.^[38]

البحث بالتقدير

ملف:Interpolation search-ar.svg

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

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

يمكن إنجاز البحث الخطي بالبحث بالتقدير. إذا كانت $A$ مصفوفة حدها الأعلى هو $R$ وحدها الأدنى $L$ ، وكانت القيمة المُستهدفة هي $T$ ، فبالإمكان تقدير موقع الهدف حسب العلاقة: $(T - A_{L}) / (A_{R} - A_{L})$ وهي حتماً قيمة تقع بين $L$ و $R$ . إذا وزعت عناصر المصفوفة عند استخدام البحث الخطي توزيعًا منتظمًا أو شبه منتظم، فإن البحث البحث بالتقدير يحتاج إلى $O (\log \log n)$ مقارنة. ^[39]^[40]

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

التتالي الجزئي

ملف:Fractional cascading-ar.svg

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

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

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

التعميم على البيانات

قالب:انظر أيضًا يُعمم البحث الاثناني ليسعمل من أنواع محددة من البيانات. أشجار البحث الاثنانية هي إحدى هذه التعميمات، فعندما يُستعلم عن عقدة ما في الشجرة، تُحدِّد الخوارزمية العقدة حيث توجد القيمة المُستهدَفة، أو الشجرة الفرعية حيث توجد تلك العقدة. ويمكن أيضاً تعميم ما سبق على نحو أشمل كما سيأتي: من أجل بيان غير موجَّهٍ ذي وزن إيجابي وعقدة ما مُستهدَفة فيه، فإنَّ استعلام الخوارزمية لعقدة ما في البيان، إما أن يكشَف عن كونها مساوية للقيمة المُستهدَفة، أو يُحدد الوصلة التي تقود إلى أقصر مسار يصل بين العقدة المُستعلَمة والعقدة المُستهدفة. خوارزمية البحث الاثناني القياسية حالة بسيطة لبيان وحيد المسار. بالمثل، فإن أشجار البحث الاثناني هي الحالة التي تكون نتيجة استعلام عقدة لا تساوي قيمتها القيمة المُستهدفة هي شجرةٌ فرعية تقع إلى يمين العقدة المُستعملة أو إلى يسارها. أما فيما يخص البيانات غير غير الموجَّهة ذات الأوزان الإيجابية، فثمة خوارزمية تُوجِد العقدة المُستهدَفة بعد $O (\log n)$ استعلام في أسوأ الحالات.^[42]

البحث الاثناني الضجيجي

ملف:Noisy binary search-ar.svg

ثمة احتمال معين بأن المقارنة غير صحيحة في البحث الاثناني الضجيجي.

تقدم خوارزميات البحث الاثناني الضجيجية حلاً في الحالات التي لا يمكن فيها مقارنة عناصر المصفوفة بشكل موثوق. في هذه الحالات، ومن أجل كل زوج من العناصر، ثمةاحتمال أن تنجز الخوارزمية مقارنة خاطئة. يمكن للبحث الاثناني الضجيجي أن يجد الموقع الصحيح للقيمة المُستهدَفة مع احتمال معين يتحكم في الموثوقية. يلزم أن تنجر كل إجرائية بحث اثناني ضجيجي عددًا من المقارنات يبلغ $(1 - τ) \frac{\log_{2} (n)}{H (p)} - \frac{10}{H (p)}$ مقارنة في المتوسط على الأقل، حيث $H (p) = - p \log_{2} (p) - (1 - p) \log_{2} (1 - p)$ هي دالة التحول الاثناني و $τ$ هو احتمالية أن يعيد الإجراء موقعاً خاطئاً.^[43]

البحث الاثناني الضجيجي حالة من لعبة ريناي وأولام،^[44] وهي نوع متفرع من لعبة الأسئلة العشرين التي يُحتمل أن تكون الإجابات خاطئة فيها.^[45]

البحث الاثناني الكمي

تُحدُّ أجهزة الحاسوب التقليدية بالحالة الأكثر سوءاً التي تُنفِّذ $⌊ \log_{2} n + 1 ⌋$ تكراراً عند إجراء البحث الاثناني. لا تزال خوارزميات البحث الاثناني الكَميّ محدودة بالنسبة $\log_{2} n$ من أجل الاستعلامات، وه تمثل عدد التكرارات في الإجراء التقليدي، ولكن العامل الثابت ذو قيمة أقل من واحد، ما يؤمِّن تعقيداً زمنياً أقل في أجهزة الحواسيب الكمية.

يتطلب إجراء أي بحث اثناني كمي دقيق، أي إجراء يعيد نتيجة صحيحة دائماً، تنفيذ $\frac{1}{π} (\ln n - 1) \approx 0.22 \log_{2} n$ استعلام على الأقل في الحالات الأكثر سوءاً، حيث $\frac{1}{π} (\ln n - 1) \approx 0.22 \log_{2} n$ هو اللغارتم الطبيعي.^[46] ثمة إجراء لبحث اثناني كمي دقيق يُنفِّذ $4 \log_{605} n \approx 0.433 \log_{2} n$ استعلاماً في أسوأ الحالات.^[47] لغرض المقارنة، فإنَّ خوارزمية غروفر، وهي الخوارزمية الكمية المثلى للبحث في قائمة غير مرتبة من العناصر، تتطلب $O (\sqrt{n})$ استعلاماً.^[48]

نبذة تاريخية

تعود جذور فكرة فرز قائمة من العناصر للسماح بالبحث فيها بسرعة أكبر إلى العصور القديمة، وأقدم مثال معروف عن ذلك هو لوح إناكيبيت آنو من بابل الذي يعود إلى حوالي عام 200 قبل الميلاد. احتوى هذا اللوح حوالي 500 رقماً مكتوباً بنظام العد الستيني ومقابلاتها مرتبةً معجمياً، ما يُسهل البحث عن البنود. بالإضافة إلى ذلك، عُثر على العديد من قوائم الأسماء المرتبة حسب حرفها الأول في جزر بحر إيجة. وهناك أيضاً الكاثُولِيكون، وهو قاموس لاتيني أنجز عام 1286م، وكان أول عمل يصف قواعد ترتيب الكلمات أبجدياً، على عكس الأسلوب السابق الذي كان يعتمد على ترتيب الأحرف الأولى فقط.^[7]

أشار جون ماكلي في عام 1946م للمرة الأولى إلى البحث الاثناني ضمن مجموعة محاضرات في مدرسة مور.^[7] في عام 1957م، نشر ويليام ويزلي بيترسون الطريقة الأولى للبحث بالتقدير.^[7]^[49] عملت كل خوارزميات البحث الاثناني المنشورة حتى عام 1960م على المصفوفات التي يكون طولها من مضاعفات العدد 2...^{[وب-إنج 1]}،^[ي] بعد ذلك نشر ديريك هنري ليمر خوارزمية بحث اثناني عملت على المصفوفات أيًا كان طولها.^[50] في عام 1962م، قدم هيرمان بوتينبروش تنفيذًا بلغة "ألغول 60" لعملية البحث الاثناني تضمن إجراء المقارنة للتحقق من مساواة العنصر للقيمة المُستهدفة في نهاية البحث، وسبّب هذا زيادةً في متوسط عدد التكرارات بمقدار واحد، ولكنه قلّل من عدد المقارنات لكل تكرار.^[6] طوّر شاندرا من جامعة ستانفورد البحث الاثناني المنتظم عام 1971م.^[7] قدّم برنارد شازيل وليونيداس جويباس في عام 1986م التتابعيَ الجزئي طريقةً لحل العديد من مُشكلات البحث في الهندسة الحسابية.^[41]^[51]

مشكلات التنفيذ

	مع أن الفكرة الرئيسة للبحث الاثناني واضحة نسبيًا، إلا أن التفاصيل يمكن أن تكون صعبة صعوبة مدهشة
—دونالد كانوث، ^[4]

عندما قدّم جون بنتلي البحث الاثناني على شكل مسألةً في دورة للمبرمجين المحترفين، وجد أن 90% منهم أخفقوا في حلها حلًا صحيحًا بعد ساعات عديدة من العمل، ويرجع ذلك أساساً إلى التنفيذ غير السليم للخوارزمية والذي يُنتج مشكلة عند التشغيل أو يُرجع قيماً خاطئة في حالات اختبار حدية نادرة.^[52] تظهر دراسة نُشرت عام 1988م وشملت عشرين كتاباً عن البرمجة أن النص البرمجي المصدري الدقيق لعملية البحث الاثناني موجود فقط في خمسة منها.^[53] بالإضافة إلى ذلك، فإن تنفيذ بنتلي الذاتي للبحث الاثناني، والذي نشره في كتابه الصادر عام 1986 بعنوان "جواهر البرمجة"، تضمَّن خطأ فيضٍ ظلَّ غير معروفٍ لأكثر من عشرين عاماً. وشمل تنفيذ مكتبة لغة البرمجة جافا الخاص بالبحث الاثناني خطأ الفيض نفسه لأكثر من تسع سنوات.^{[وب-إنج 2]}

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

قد تحدث حلقة لا نهائية إذا لم يُحدَّد شروط الخروج من الحلقة تحديدًا صحيحًا. عندما تتجاوز قيمةُ $L$ قيمةَ $R$ ، يُخفِق البحث ويَلزم أن يُبلَّغ عن ذلك. يلزم أيضًا الخروج من الحلقة عند العثور على العنصر المُستهدَف، أمَّا في حالة التنفيذ الذي يُؤجَّل الفحص إلى النهاية، يلزم التحقق من نجاح البحث أو إخفاقه عند الانتهاء. وجد بنتلي أن معظم المبرمجين الذين نفذوا البحث الاثناني تنفيذًا غير صحيح ارتكبوا خطأ ما في تحديد شروط الخروج.^[7]^[55]

الدعم في المكتبات المعيارية

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

توفِّر لغة سي الدالة ()bsearch في مكتبتها المعيارية، وهي دالة تُنفَّذ اعتماداً على البحث الاثناني، مع أن المعيار الرسمي لا يتطلَّب ذلك.^{[وب-إنج 3]}
توفر مكتبة النماذج القياسية في سي++ الدوال ()binary_search و()lower_bound و ()upper_bound و()equal_range.^[56]
توفِّر مكتبة لغة دي القياسية المُسمَّاة فوبوس، في الوحدة std.range نوع SortedRange (وهو يُرجع بواسطة الدوال ()sort و()assumeSorted)، بالإضافة للدوال الأعضاء ()contains و()equaleRange و()equaleRange و()lowerBound و()trisect، التي تستخدم أيضاً تقنيات البحث الاثناني افتراضياً مع النطاقات التي توفر وصولاً عشوائياً.^{[وب-إنج 4]}
توفر كوبول فعل SEARCH ALL لإجراء عمليات بحث اثناني على جداول كوبول المرتبة.^{[وب-إنج 5]}

تحتوي حزمة مكتبة غو القياسية للفرز على دوال البحث Search ، SearchInts ، SearchFloat64s، وSearchStrings، التي تُنفِّذ البحث الاثناني العام، وكذلك تطبيقات محددة للبحث في شرائح الأعداد الصحيحة وأرقام الفاصلة العشرية والسلاسل على التوالي.^{[وب-إنج 6]}
تقدِّم جافا مجموعة من الدوال الأعضاء التي تحمِّل الدالة ()binarySearch الثابتة بشكل زائد في أصناف المصفوفات والمجموعات في حزمة java.util القياسية لإجراء عمليات البحث الاثناني على مصفوفات جافا وعلى القوائم List، على التوالي.^{[وب-إنج 7]}

تقدِّم مايكروسوفت دوت نت فريموورك إصدارات عامة ثابتة من خوارزمية البحث الاثناني في الأصناف الأساسية في مجموعتها. مثال على ذلك هو الدالة العضو System.Array BinarySearch<T>(T[] array, T value).^{[وب-إنج 8]}

بالنسبة إلى سي-الكائنية، يوفر إطار العمل المُسمَّى NSArray -indexOfObject:inSortedRange:options:usingComparator: دالةً عضو في ماك أو إس إكس 10.6+.^{[وب-إنج 9]} يحتوي إطار عمل آبل فونديشين سي (الإنجليزية: Apple Foundation C) الأساسي أيضاً على دالة ()CFArrayBSearchValues.^{[وب-إنج 10]}
توفِّر بايثون وحدة bisect.^{[وب-إنج 11]}
يتضمن صنف المصفوفة في روبي دالة عضو اسمها bsearch تشمل على تطابق تقريبي.^[57]

الهوامش

^ الأسماء الأصل على الترتيب: (الإنجليزية: Half-interval search, logarithmic search, and binary chop).
^ اسما المتغيرين هما الحرفان الأولان من كلمتي يسار (الإنجليزية: Left) ويمين (الإنجليزية: Right) على الترتيب.
^ يمكن تمثيل أي خوارزمية بحث تستند إلى المقارنات فقط باستخدام شجرة مقارنة اثنانية. المسار الداخلي هو أي مسار من الجذر إلى العقدة المدروسة. ليكن $I$ طول المسار الداخلي، أي مجموع أطوال جميع المسارات الداخلية. إذا كان من احتمال البحث عن كل العناصر متساوياً، فإن طول المسار الوسطي سيكون $1 + 1 / n$ ، أو ببساطة واحد مضافاً إليه متوسط أطوال المسارات الداخلية في الشجرة كلها. وهذا صحيح لأن المسارات الداخلية تمثل العناصر التي تقارنها خوارزمية البحث مع الهدف. أمَّا أطوال هذه المسارات الداخلية فتُمثِّل عدد التكرارات بعد تجاوز العقدة الجذر. إن إضافة متوسط هذه الأطوال إلى تكرار واحد لازم لتجاوز العقدة الجذر يعطي طول المسار الوسطي. بناءً على ذلك، ولتقليل متوسط عدد المقارنات، يجب تصغير طول المسار الداخلي $I$ . لقد اتضح أن شجرة البحث الاثناني تقلل من طول المسار الداخلي، فقد أثبت دونالد نوث أن طول المسار الخارجي، أي طول المسار المار بجميع العقد التي تمتلك بالفعل ابنين، يَصغر عندما توجد العقد الخارجية، أي العقد التي لا أبناء لها، في مستويين متتاليين من الشجرة. ينطبق هذا أيضاً على المسارات الداخلية لأن طول المسار الداخلي $I$ مرتبط خطياً بطول المسار الخارجي $E$ . فيما يخص أي شجرة تضمُّ $n$ عقدة، فإن $I = E - 2 n$ . عندما تحتوي كل الأشجار الفرعية على عدد متماثل من العقد، أو عندما تُقسَّم المصفوفة بالتساوي إلى نصفين بعد كل تكرار، فإنَّ العقد الخارجية وكذلك العقد الرئيسية الداخلية تقع داخل مستويين. ويترتب على ذلك أن البحث الاثناني يقلل من عدد المقارنات المتوسطة عندما يكون شجرة المقارنة أقل طول ممكن للمسار الداخلي.^[12]
^ أظهر دونالد نوث على حاسوبه المُسمى ميكس (الإنجليزية: MIX)، والذي صممه ليُمثِّل حاسوباً عادياً، أن متوسط زمن تشغيل هذا التنفيذ لعملية بحث الناجح هو $17.5 \log_{2} n + 17$ وحدة زمن مقارنةً مع $18 \log_{2} n - 16$ وحدة زمن من أجل البحث الاثناني المنتظَم. ينمو التعقيد الزمني لهذا التنفيذ بشكل أبطأ قليلاً، ولكن على حساب التعقيد الابتدائي المرتفع.^[17]
^ أجرى دونالد نوث تحليلاً منهجياً لأداء الوقت لخوارزميتي البحث هاتين. في حاسوب ميكس، والذي صممه نوث لتمثيل حاسوب عادي، استغرق البحث الاثناني وسطياً $18 \log_{n} - 16$ وحدة زمنية من أجل بحث ناجح، بينما استغرق البحث الخطي مع عقدة رصد ^[English] في نهاية القائمة $1.75 n + 8.5 - n mod 2 / 4 n$ وحدة زمنية. للبحث الخطي تعقيد ابتدائي أقل لأنه يتطلب عميلات حسابية أقل، لكن تعقيده يتنمو ليتفوق بسرعة على البحث الاثناني. في حاسوب ميكس، يتفوق البحث الاثناني فقط على البحث الخطي باستخدام عقدة الرصد إذا كانت المتراجحة $n > 44$ مُحققة.^[12]^[23]
^ سيؤدي إدخال القيم وفق تتابع مُرتَّب أو في نمط المفتاح الأدنى والأعلى (الإنجليزية: Lowest-highest key) إلى شجرة بحث اثنانية تزيد متوسط وقت البحث ووقت البحث في أسوأ الحالات.^[27]
^ في بعض تطبيقات جدول التجزئة من الممكن إنجاز البحث خلال وقت ثابت مضمون.^[32]
^ هذا لأن مجرد تعيين كل البتات التي تشير إليها وظائف التجزئة لمفتاح معين يمكن أن يؤثر في استعلامات المفاتيح الأخرى التي لها موقع تجزئة مشترك لواحدة أو أكثر من الوظائف.^[35]
^ ثمة تحسينات لمرشح بلوم لتبسيط تعقيده أو لدعم الحذف، على سبيل المثال، يستعمل مرشحُ كوكو تجزئةَ كوكو من أجل اكتساب هذه الميزات.^[35]
^ أي مصفوفة فهرس أكبر عنصر فيها: 1، 3، 7، 15، 31...^{[وب-إنج 1]}

ملحق: مسرد المصطلحات الإنجليزية

مَسرد المفردات وفق الترتيب الأبجدي
الغول 60	Algol 60
وقت ثابت مستوفى	Amortized constant time
تطابق تقريبي	Approximate match
استعلام تقريبي	Approximate query
فيض حسابي	Arithmetic overflow
مصفوفة ترابطية	Associative array
شجرة بحث اثنانية متوازنة	Balanced binary search tree
تمثيل O الكبرى	Big O notation
قطع اثناني	Binary chop
دالة التحول الاثناني	Binary entropy function
لغارتم اثناني	Binary logarithm
بحث اثناني	Binary search
شجرة بحث اثنانية	Binary search tree
طريقة التصنيف الاثناني	Bisection method
بت	Bit
مصفوفة بت	Bit array
مرشح بلوم	Bloom filter
قائمة محدودة	Bounded list
شجرة بي	B-tree
ذاكرة مخبئية	Cache
كاثوليكون	Catholicon
المتمم الصحيح الأعلى	Ceiling
دالة المتمم الصحيح الأعلى	Ceiling function
هندسة رياضية حاسوبية	Computational geometry
قيم دالة مستمرة	Continuous function values
استخراج البيانات	Data mining
بنية بيانات	Data structure
قاعدة بيانات	Database
حاسوب عشري	Decimal computer
حذف	Deletion
اشتقاق حالة متوسطة	Derivation of average case
حالة حدية	Edge case
تطابق تقريبي فعال	Efficient approximate matching
تطابق تام	Exact matching
بحث أسي	Exponential search
ذاكرة خارجية	External memory
إيجابيات مزيفة	False positives
نظام ملفات	File system
مصفوفة مرتبة منتهية العناصر	Finite sorted array
فاصلة متحركة	Floating-point
الجزء الصحيح لأي عدد صحيح	Floor
دالة الجزء الصحيح لأي عدد صحيح	Floor function
تتالي جزئي	Fractional cascading
شجرة الدمج	Fusion trees
التعميم على الرسوم البيانية	Generalization to graphs
خوارزمية غروفر	Grover's algorithm
البحث المحدد بفاصل المنتصف	Half-Interval search
قرص صلب	Hard disk
دالة تجزئة	Hash function
جدول تجزئة	Hash table
تجزئة	Hashing
جدول إناكيبيت آنو	Inakibit-Anu tablet
فهرس	Index
تكرار ابتدائي	Initial iteration
إدراج	Insertion
مسار داخلي	Internal path
بحث بالتقدير	Interpolation search
فاصل	Interval
إجراء تكراري	Iterative procedure
جافا	Java
مصفوفة جودي	Judy array
ترتيب معجمي	Lexicographical order
استيفاء خطي	Linear interpolation
سبر خطي	Linear probing
بحث خطي	Linear search
قائمة مرتبطة	Linked list
محلية المرجع	Locality of reference
بحث لغارتمي	Logarithmic search
وقت لغارتمي	Logarithmic time
جدول بحث	Lookup table
فرز بالمرج	Merge sort
لغارتم طبيعي	Natural logarithm
الجار الأقرب	Nearest neighbor
بحث اثناني ضجيجي	Noisy binary search
خطأ الفيض	Overflow error
مؤشر	Pointer
معالِج	Processor
شبه رماز	Pseudocode
خوارزمية كمومية	Quantum algorithm
بحث اثناني كمومي	Quantum binary search
حواسيب كمومية	Quantum computers
حساب كمومي	Quantum computing
فرز سريع	Quicksort
ذاكرة الوصول العشوائي	Random acess memory
استعلام المجال	Range query
مرتبة	Rank
استعلام المرتبة	Rank query
مقلوب عدد	Reciprocals
سجل	Record
لعبة ريناي وأولام	Rényi-Ulam game
إرجاع $x$	$x$ Return
عقدة الجذر	Root node
خوارزمية بحث	Search algorithm
ضبط العضوية	Set membership
نظام عد ستيني	Sexagesimal
عقدة مفردة	Single node
مصفوفة مفروزة	Sorted array
خوارزمية فرز	Sorting algorithm
تعقيد الفضاء	Space complexity
اللاحق	Successor
سلسلة محرفية	String
بنية	Structure
دالة فرعية	Subroutine
قيمة مستهدفة / قيمة الهدف	Target value
تعقيد الزمن	Time complexity
شجرة	Tree
شجرة تري	Tries
رسم بياني غير موجه وموزون	Undirected positively weighted graph
بحث اثناني منتظم	Uniform binary search
عدد صحيح بدون إشارة	Unsigned integer
شجرة فان إيمد بواس	Van Emde Boas tree
الحالة الأسوأ	Worst case

انظر أيضًا

المراجع

فهرس الإحالات

المنشورات: بالعربية

^ الجمعية السورية (2000)، ص. 48.
^ الزهيري (2006)، ص. 54.
^ ^أ ^ب مجمع القاهرة (2003)، ص. 36.

بالإنجليزية

^ Cormen (2009), p. 39 .
^ ^أ ^ب Flores (1971), p. 602-603 .
^ Williams (1976), p. 95-101 .
^ ^أ ^ب ^ت ^ث ^ج Knuth (1998), p. 411-415 .
^ Butterfield (2016), p. 46 .
^ ^أ ^ب ^ت Bottenbruch (1962), p. 161-221 .
^ ^أ ^ب ^ت ^ث ^ج ^ح ^خ Knuth (1998), p. 420-422 .
^ ^أ ^ب Kasahara (2006), p. 8-9 .
^ ^أ ^ب ^ت Sedgewick (2011), p. 367 .
^ ^أ ^ب ^ت Goldman (2008), p. 461-463 .
^ Sedgewick (2011), p. 368 .
^ ^أ ^ب ^ت ^ث ^ج ^ح ^خ ^د ^ذ ^ر ^ز ^س Knuth (1998), p. 413-415 .
^ Knuth (1998), p. 410 .
^ Chang2003, p. 169 .
^ Shannon (1948), p. 423-379 .
^ ^أ ^ب ^ت Knuth (1997), p. 399-405 .
^ ^أ ^ب Knuth (1998), p. 425 .
^ Rolfe (1997), p. 15-19 .
^ Khuong (2017), p. 1-39 .
^ Knuth (1997), p. 244-253 .
^ ^أ ^ب ^ت ^ث Beame (2002), p. 38-72 .
^ Knuth (1998), p. 409-426 .
^ Knuth (1998), p. 705 .
^ Knuth (1998), p. 180-197 .
^ Sedgewick (2011), p. 366-369 .
^ Sedgewick (2011), p. 406-414 .
^ Knuth (1998), p. 430-431 .
^ Sedgewick (2011), p. 387-389 .
^ [a] Knuth (1998), p. 356-379 .
[b] Knuth (1998), p. 481-492 .
^ Knuth (1998), p. 513 .
^ Dietzfelbinger (1994), p. 738–761 .
^ Knuth (1998), p. 547-549 .
^ Knuth (2011), p. 133-202 .
^ Bloom (1970), p. 422–426 .
^ ^أ ^ب Fan (2014), p. 75-88 .
^ Knuth (1998), p. 414-415 .
^ Knuth (1998), p. 141 .
^ Moffat (2002), p. 33 .
^ ^أ ^ب ^ت Knuth (1998), p. 419-420 .
^ [a] Knuth (1998), p. 425 .
[b] Perl (1978), p. 550–553 .
^ ^أ ^ب ^ت Chazelle (2001), p. 322–329 .
^ Emamjomeh-Zadeh (2016), p. 519–532 .
^ [a] Rivest (1978), p. 227–232 .
[b] Pelc (1989), p. 185-202 .
[c] Ben-Or (2007), p. 221-230 .
^ Pelc (2002), p. 71-109 .
^ Rényi (1961), p. 515-516 .
^ Høyer (2002), p. 429–448 .
^ Childs (2007), p. 1-8 .
^ Grover (1996), p. 212–219 .
^ Peterson (1957), p. 130-146 .
^ Lehmer (1960), p. 180–181 .
^ [a] Chazelle (1986a), p. 133–162 .
[b] Chazelle (1986b), p. 163–191 .
^ Bentley (1999), p. 33-34 .
^ Pattis (1988), p. 190–194 .
^ Ruggieri (2003), p. 67-71 .
^ Bentley (1999), p. 39-40 .
^ Stroustrup (2013), p. 945 .
^ Fitzgerald (2015), p. 152 .

الوب: بالإنجليزية

^ ^أ ^ب "A000225". The OEIS Foundation. (بEnglish). Archived from the original on 2016-06-08. Retrieved 2020-07-07.
^ Joshua Bloch (2 Jun 2006). "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken". Google AI Blog (بEnglish). Archived from the original on 2016-04-01. Retrieved 2020-07-06.
^ "bsearch - binary search a sorted table". opengroup.org (بEnglish). Archived from the original on 2016-03-21. Retrieved 2020-07-06.
^ "std.range". dlang.org (بEnglish). Archived from the original on 2018-11-27. Retrieved 2020-07-06.
^ "COBOL ANSI-85, Programming Reference Manual, Volume 1: Basic Implementation" (PDF). unisys (بEnglish). Apr 2015. p. 8-6. Archived from the original (PDF) on 2020-01-25. Retrieved 2020-07-06.
^ "Package sort". golang (بEnglish). Apr 2015. Archived from the original on 2020-04-26. Retrieved 2020-07-06.
^ [a] "Class Arrays". Oracle (بEnglish). Archived from the original on 2020-06-14. Retrieved 2020-07-06.
[b] "Class Collections". Oracle (بEnglish). Archived from the original on 2020-06-14. Retrieved 2020-07-06.
^ "List<T>.BinarySearch Method". microsoft (بEnglish). Archived from the original on 2016-05-07. Retrieved 2020-07-06.
^ "NSArray". apple (بEnglish). Archived from the original on 2020-03-11. Retrieved 25–01–2026.{{استشهاد ويب}}: صيانة الاستشهاد: تنسيق التاريخ (link)
^ "CFArray". apple (بEnglish). Archived from the original on 2016-04-20. Retrieved 2020-07-06.
^ "8.6. bisect — Array bisection algorithm". python (بEnglish). Archived from the original on 2018-03-25. Retrieved 2020-07-06.

ثبت المراجع

المقالات المُحكَّمة

Q56039276، QID:Q56039276
Q724029، QID:Q724029
Q55889031، QID:Q55889031
Q137886494، QID:Q137886494
Q137884499، QID:Q137884499
Q56039262، QID:Q56039262
Q55889030، QID:Q55889030
Q54260361، QID:Q54260361
Q56039261، QID:Q56039261
Q56039264، QID:Q56039264
Q56039269، QID:Q56039269
Q56039273، QID:Q56039273
Q56039274، QID:Q56039274
Q56039275، QID:Q56039275
Q56039268، QID:Q56039268
Q55878437، QID:Q55878437
Q55878438، QID:Q55878438
Q56039263، QID:Q56039263
Q56039265، QID:Q56039265
Q55889025، QID:Q55889025
Q56039270، QID:Q56039270
Q56039267، QID:Q56039267
Q137876051، QID:Q137876051
Q56039271، QID:Q56039271
Q55889027، QID:Q55889027
Q137874163، QID:Q137874163
Q130961938، QID:Q130961938

الكتب: بالعربية

Q108408025، QID:Q108408025
Q113638576، QID:Q113638576
Q123157933، QID:Q123157933

بالإنجليزية

Q47755251، QID:Q47755251
Q137835469، QID:Q137835469
Q67955975، QID:Q67955975
Q56039277، QID:Q56039277
Q137842077، QID:Q137842077
Q137835889، QID:Q137835889
Q137836179، QID:Q137836179
Q110418801، QID:Q110418801
Q47757005، QID:Q47757005
Q137840491، QID:Q137840491
Q122168724، QID:Q122168724
Q137886871، QID:Q137886871
Q123266313، QID:Q123266313

[9] الأسماء الأصل على الترتيب: (الإنجليزية: Half-interval search, logarithmic search, and binary chop).

[10] اسما المتغيرين هما الحرفان الأولان من كلمتي يسار (الإنجليزية: Left) ويمين (الإنجليزية: Right) على الترتيب.

[20] يمكن تمثيل أي خوارزمية بحث تستند إلى المقارنات فقط باستخدام شجرة مقارنة اثنانية. المسار الداخلي هو أي مسار من الجذر إلى العقدة المدروسة. ليكن $I$ طول المسار الداخلي، أي مجموع أطوال جميع المسارات الداخلية. إذا كان من احتمال البحث عن كل العناصر متساوياً، فإن طول المسار الوسطي سيكون $1 + 1 / n$ ، أو ببساطة واحد مضافاً إليه متوسط أطوال المسارات الداخلية في الشجرة كلها. وهذا صحيح لأن المسارات الداخلية تمثل العناصر التي تقارنها خوارزمية البحث مع الهدف. أمَّا أطوال هذه المسارات الداخلية فتُمثِّل عدد التكرارات بعد تجاوز العقدة الجذر. إن إضافة متوسط هذه الأطوال إلى تكرار واحد لازم لتجاوز العقدة الجذر يعطي طول المسار الوسطي. بناءً على ذلك، ولتقليل متوسط عدد المقارنات، يجب تصغير طول المسار الداخلي $I$ . لقد اتضح أن شجرة البحث الاثناني تقلل من طول المسار الداخلي، فقد أثبت دونالد نوث أن طول المسار الخارجي، أي طول المسار المار بجميع العقد التي تمتلك بالفعل ابنين، يَصغر عندما توجد العقد الخارجية، أي العقد التي لا أبناء لها، في مستويين متتاليين من الشجرة. ينطبق هذا أيضاً على المسارات الداخلية لأن طول المسار الداخلي $I$ مرتبط خطياً بطول المسار الخارجي $E$ . فيما يخص أي شجرة تضمُّ $n$ عقدة، فإن $I = E - 2 n$ . عندما تحتوي كل الأشجار الفرعية على عدد متماثل من العقد، أو عندما تُقسَّم المصفوفة بالتساوي إلى نصفين بعد كل تكرار، فإنَّ العقد الخارجية وكذلك العقد الرئيسية الداخلية تقع داخل مستويين. ويترتب على ذلك أن البحث الاثناني يقلل من عدد المقارنات المتوسطة عندما يكون شجرة المقارنة أقل طول ممكن للمسار الداخلي.^[12]

[25] أظهر دونالد نوث على حاسوبه المُسمى ميكس (الإنجليزية: MIX)، والذي صممه ليُمثِّل حاسوباً عادياً، أن متوسط زمن تشغيل هذا التنفيذ لعملية بحث الناجح هو $17.5 \log_{2} n + 17$ وحدة زمن مقارنةً مع $18 \log_{2} n - 16$ وحدة زمن من أجل البحث الاثناني المنتظَم. ينمو التعقيد الزمني لهذا التنفيذ بشكل أبطأ قليلاً، ولكن على حساب التعقيد الابتدائي المرتفع.^[17]

[31] أجرى دونالد نوث تحليلاً منهجياً لأداء الوقت لخوارزميتي البحث هاتين. في حاسوب ميكس، والذي صممه نوث لتمثيل حاسوب عادي، استغرق البحث الاثناني وسطياً $18 \log_{n} - 16$ وحدة زمنية من أجل بحث ناجح، بينما استغرق البحث الخطي مع عقدة رصد ^[English] في نهاية القائمة $1.75 n + 8.5 - n mod 2 / 4 n$ وحدة زمنية. للبحث الخطي تعقيد ابتدائي أقل لأنه يتطلب عميلات حسابية أقل، لكن تعقيده يتنمو ليتفوق بسرعة على البحث الاثناني. في حاسوب ميكس، يتفوق البحث الاثناني فقط على البحث الخطي باستخدام عقدة الرصد إذا كانت المتراجحة $n > 44$ مُحققة.^[12]^[23]

[36] سيؤدي إدخال القيم وفق تتابع مُرتَّب أو في نمط المفتاح الأدنى والأعلى (الإنجليزية: Lowest-highest key) إلى شجرة بحث اثنانية تزيد متوسط وقت البحث ووقت البحث في أسوأ الحالات.^[27]

[42] في بعض تطبيقات جدول التجزئة من الممكن إنجاز البحث خلال وقت ثابت مضمون.^[32]

[46] هذا لأن مجرد تعيين كل البتات التي تشير إليها وظائف التجزئة لمفتاح معين يمكن أن يؤثر في استعلامات المفاتيح الأخرى التي لها موقع تجزئة مشترك لواحدة أو أكثر من الوظائف.^[35]

[47] ثمة تحسينات لمرشح بلوم لتبسيط تعقيده أو لدعم الحذف، على سبيل المثال، يستعمل مرشحُ كوكو تجزئةَ كوكو من أجل اكتساب هذه الميزات.^[35]

[63] أي مصفوفة فهرس أكبر عنصر فيها: 1، 3، 7، 15، 31...^{[وب-إنج 1]}

[1] الجمعية السورية (2000)، ص. 48.

[4] الزهيري (2006)، ص. 54.

[Dic1-5] أ ^ب مجمع القاهرة (2003)، ص. 36.

[REF-4-2] Cormen (2009), p. 39 .

[REF-6-3] أ ^ب Flores (1971), p. 602-603 .

[REF-1-6] Williams (1976), p. 95-101 .

[REF-7-7] أ ^ب ^ت ^ث ^ج Knuth (1998), p. 411-415 .

[REF-3-8] Butterfield (2016), p. 46 .

[REF-8-11] أ ^ب ^ت Bottenbruch (1962), p. 161-221 .

[REF-9-12] أ ^ب ^ت ^ث ^ج ^ح ^خ Knuth (1998), p. 420-422 .

[REF-10-13] أ ^ب Kasahara (2006), p. 8-9 .

[REF-11-14] أ ^ب ^ت Sedgewick (2011), p. 367 .

[REF-12-15] أ ^ب ^ت Goldman (2008), p. 461-463 .

[REF-13-16] Sedgewick (2011), p. 368 .

[REF-14-17] أ ^ب ^ت ^ث ^ج ^ح ^خ ^د ^ذ ^ر ^ز ^س Knuth (1998), p. 413-415 .

[REF-15-18] Knuth (1998), p. 410 .

[REF-16-19] Chang2003, p. 169 .

[REF-17-21] Shannon (1948), p. 423-379 .

[REF-18-22] أ ^ب ^ت Knuth (1997), p. 399-405 .

[REF-19-23] أ ^ب Knuth (1998), p. 425 .

[REF-20-24] Rolfe (1997), p. 15-19 .

[REF-21-26] Khuong (2017), p. 1-39 .

[REF-22-27] Knuth (1997), p. 244-253 .

[REF-23-28] أ ^ب ^ت ^ث Beame (2002), p. 38-72 .

[REF-25-29] Knuth (1998), p. 409-426 .

[REF-24-30] Knuth (1998), p. 705 .

[REF-26-32] Knuth (1998), p. 180-197 .

[REF-27-33] Sedgewick (2011), p. 366-369 .

[REF-28-34] Sedgewick (2011), p. 406-414 .

[REF-29-35] Knuth (1998), p. 430-431 .

[REF-30-37] Sedgewick (2011), p. 387-389 .

[38] [a] Knuth (1998), p. 356-379 .
[b] Knuth (1998), p. 481-492 .

[REF-33-39] Knuth (1998), p. 513 .

[REF-35-40] Dietzfelbinger (1994), p. 738–761 .

[REF-34-41] Knuth (1998), p. 547-549 .

[43] Knuth (2011), p. 133-202 .

[REF-40-44] Bloom (1970), p. 422–426 .

[REF-39-45] أ ^ب Fan (2014), p. 75-88 .

[REF-41-48] Knuth (1998), p. 414-415 .

[REF-42-49] Knuth (1998), p. 141 .

[REF-43-50] Moffat (2002), p. 33 .

[REF-44-51] أ ^ب ^ت Knuth (1998), p. 419-420 .

[52] [a] Knuth (1998), p. 425 .
[b] Perl (1978), p. 550–553 .

[REF-47-53] أ ^ب ^ت Chazelle (2001), p. 322–329 .

[REF-49-54] Emamjomeh-Zadeh (2016), p. 519–532 .

[55] [a] Rivest (1978), p. 227–232 .
[b] Pelc (1989), p. 185-202 .
[c] Ben-Or (2007), p. 221-230 .

[REF-53-56] Pelc (2002), p. 71-109 .

[57] Rényi (1961), p. 515-516 .

[REF-55-58] Høyer (2002), p. 429–448 .

[59] Childs (2007), p. 1-8 .

[REF-57-60] Grover (1996), p. 212–219 .

[REF-58-61] Peterson (1957), p. 130-146 .

[REF-60-64] Lehmer (1960), p. 180–181 .

[REF-62-65] [a] Chazelle (1986a), p. 133–162 .
[b] Chazelle (1986b), p. 163–191 .

[REF-63-66] Bentley (1999), p. 33-34 .

[67] Pattis (1988), p. 190–194 .

[69] Ruggieri (2003), p. 67-71 .

[70] Bentley (1999), p. 39-40 .

[REF-69-72] Stroustrup (2013), p. 945 .

[81] Fitzgerald (2015), p. 152 .

[REF-59-62] أ ^ب "A000225". The OEIS Foundation. (بEnglish). Archived from the original on 2016-06-08. Retrieved 2020-07-07.

[68] Joshua Bloch (2 Jun 2006). "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken". Google AI Blog (بEnglish). Archived from the original on 2016-04-01. Retrieved 2020-07-06.

[71] "bsearch - binary search a sorted table". opengroup.org (بEnglish). Archived from the original on 2016-03-21. Retrieved 2020-07-06.

[73] "std.range". dlang.org (بEnglish). Archived from the original on 2018-11-27. Retrieved 2020-07-06.

[74] "COBOL ANSI-85, Programming Reference Manual, Volume 1: Basic Implementation" (PDF). unisys (بEnglish). Apr 2015. p. 8-6. Archived from the original (PDF) on 2020-01-25. Retrieved 2020-07-06.

[75] "Package sort". golang (بEnglish). Apr 2015. Archived from the original on 2020-04-26. Retrieved 2020-07-06.

[76] [a] "Class Arrays". Oracle (بEnglish). Archived from the original on 2020-06-14. Retrieved 2020-07-06.
[b] "Class Collections". Oracle (بEnglish). Archived from the original on 2020-06-14. Retrieved 2020-07-06.

[77] "List<T>.BinarySearch Method". microsoft (بEnglish). Archived from the original on 2016-05-07. Retrieved 2020-07-06.

[78] "NSArray". apple (بEnglish). Archived from the original on 2020-03-11. Retrieved 25–01–2026.{{استشهاد ويب}}: صيانة الاستشهاد: تنسيق التاريخ (link)

[79] "CFArray". apple (بEnglish). Archived from the original on 2016-04-20. Retrieved 2020-07-06.

[80] "8.6. bisect — Array bisection algorithm". python (بEnglish). Archived from the original on 2018-03-25. Retrieved 2020-07-06.

[عر 1]

[1]

[2]

[عر 2]

[عر 3]

[3]

[4]

[5]

[أ]

[ب]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[ج]

[15]

[16]

[17]

[18]

[د]

[19]

[20]

[21]

[22]

[ه]

[24]

[25]

[26]

[و]

[28]

[29]

[30]

[31]

[ز]

[33]

[34]

[ح]

[ط]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[وب-إنج 1]

[ي]

[50]

[51]

[52]

[53]

[وب-إنج 2]

[54]

[55]

[وب-إنج 3]

[56]

[وب-إنج 4]

[وب-إنج 5]

[وب-إنج 6]

[وب-إنج 7]

[وب-إنج 8]

[وب-إنج 9]

[وب-إنج 10]

[وب-إنج 11]

[57]

[23]

[27]

[32]

[35]

@@ سطر 813: / سطر 813: @@
 == انظر أيضًا ==
 {{قائمة أعمدة|عدد الأعمدة=2|الأعمدة=
 * [[طريقة التنصيف]]
@@ سطر 893: / سطر 892: @@
 {{نهاية المراجع}}
 {{بنى البيانات والخورازميات}}
 {{شريط محتوى متميز|1=مختارة|التاريخ=17 نوفمبر 2020|النسخة=51526457|تاريخ مراجعة الزملاء=30 أغسطس 2020}}

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