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

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

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

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

الخوارزمية

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

إجراء

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

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

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

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

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

إجراء بديل

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

نشر هيرمان بوتنبروش أول تطبيق لحذف هذا الفحص في عام 1962. ^{[ 8 ]}^{[ 9 ]}

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

أين ceilدالة السقف؟ الشفرة الزائفة لهذه النسخة هي:

دالة binary_search_alternative(A, n, T) هي L := 0 R := n − 1 بينما L != R نفّذ m := L + ceil((R - L) / 2) إذا كانت A[m] > T فإن R := m − 1 وإلا : L := m إذا كانت A[L] = T، فأرجع L، وإلا فأرجع غير ناجح.

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

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

إجراء إيجاد العنصر الأيسر

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

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

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

أين floorتوجد دالة الجزء الصحيح (floor)؟ الشفرة الزائفة لهذه النسخة هي:

دالة البحث الثنائي الأيسر (A، n، T): L := 0 R := n بينما L < R: m := L + floor((R - L) / 2) إذا كانت A[m] < T: L := m + 1 آخر : R := m إرجاع L

إجراء إيجاد العنصر الأقصى يمينًا

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

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

لو $R>0$ و $A_{R-1}=T$ ، ثم $A_{R-1}$ هو العنصر الأقصى يمينًا الذي يساوي $T$ حتى لو $T$ ليس موجوداً في المصفوفة، $nR$ يمثل عدد العناصر في المصفوفة التي تزيد عن $T$ .

أين floorتوجد دالة الجزء الصحيح (floor)؟ الشفرة الزائفة لهذه النسخة هي:

دالة البحث الثنائي عن أقصى اليمين (A، n، T): L := 0 R := n بينما L < R: m := L + floor((R - L) / 2) إذا كانت A[m] > T: R := m آخر : L := m + 1 أعد R - 1

نتائج مطابقة تقريبية

يمكن تكييف البحث الثنائي لحساب التطابقات التقريبية. في المثال أعلاه، يظهر الترتيب، والسابق، واللاحق، وأقرب جار للقيمة المستهدفة. $5$ ، وهو ليس موجوداً في المصفوفة.

{\displaystyle 5} — يمكن تكييف البحث الثنائي لحساب التطابقات التقريبية. في المثال أعلاه، يظهر الترتيب، والسابق، واللاحق، وأقرب جار للقيمة المستهدفة. $5$ ، وهو ليس موجوداً في المصفوفة.

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

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

أداء

{\displaystyle [20,30,40,50,80,90,100]} — شجرة تمثل البحث الثنائي. المصفوفة التي يتم البحث فيها هنا هي $[20,30,40,50,80,90,100]$ والقيمة المستهدفة هي $40$ .

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

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

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

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

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

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

تعقيد المساحة

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

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

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

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

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

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

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

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

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

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

$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$

باستبدال المعادلة بـ $I(n)$ في المعادلة لـ $T(n)$ [ ¹⁴^]

$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$

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

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

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

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

$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}$

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

$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 مقارنة في المتوسط. يتحقق أحد أشكال الخوارزمية مما إذا كان العنصر الأوسط مساويًا للهدف في نهاية البحث. في المتوسط، يُلغي هذا نصف مقارنة من كل دورة. يُقلل هذا قليلاً من الوقت المستغرق لكل دورة على معظم أجهزة الكمبيوتر. ومع ذلك، فإنه يضمن أن يستغرق البحث الحد الأقصى من الدورات، بإضافة دورة واحدة في المتوسط. ولأن حلقة المقارنة تُنفذ فقط ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ في أسوأ الأحوال، لا تعوض الزيادة الطفيفة في الكفاءة لكل تكرار عن التكرار الإضافي إلا في الحالات الكبيرة جدًا. ${\textstyle n}$ [ ^ج^]^[¹⁸^]^[¹⁹^]

اعتبارات إضافية

تكلفة المقارنة

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

تُتيح المقارنة السريعة للأعداد العشرية إمكانية المقارنة كأعداد صحيحة. مع ذلك، يُنشئ هذا النوع من المقارنة ترتيبًا كليًا ، ما يجعل كل قيمة عشرية تُقارن بشكل مختلف عن غيرها، وتُعامل في الوقت نفسه على أنها مماثلة لنفسها. وهذا يختلف عن المقارنة التقليدية حيث يُفترض أن تكون -0.0 مماثلة لـ 0.0، ولا يُفترض أن تُقارن NaN بشكل مماثل لأي قيمة أخرى، بما في ذلك نفسها. ^{[ 20 ]}^{[ 21 ]}

التنبؤ بالفروع

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

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

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

أشار بول خونغ إلى أن البحث الثنائي على مصفوفات كبيرة (≥ 512 كيلوبايت) بحجم قوة العدد 2 يُسبب عادةً مشكلة إضافية تتعلق بكيفية تنفيذ ذاكرة التخزين المؤقت لوحدة المعالجة المركزية. تحديدًا، غالبًا ما يتم تنفيذ مخزن البحث الجانبي للترجمة (TLB) كذاكرة قابلة للعنونة بالمحتوى (CAM)، حيث يكون "المفتاح" عادةً هو البتات الدنيا للعنوان المطلوب. عند البحث في مصفوفة بحجم قوة العدد 2، يميل الوصول إلى عناوين الذاكرة التي لها نفس البتات الدنيا إلى الحدوث، مما يُسبب تصادمات ("التداخل") مع "المفتاح" المستخدم لجلب CAM. عادةً ما يكون مخزن البحث الجانبي للترجمة (TLB) ترابطيًا رباعي الاتجاهات، مما يعني أنه يستطيع التعامل مع أربعة عناوين كحد أقصى تصل إلى نفس "المفتاح"، وبعد ذلك يحدث تذبذب في أداء مخزن البحث الجانبي للترجمة (TLB) . (على الرغم من أن مستويات ذاكرة التخزين المؤقت الأخرى لوحدة المعالجة المركزية تستخدم أيضًا إعدادًا مشابهًا، إلا أنها تدير مساحات أصغر بعدد مسارات أكبر، عادةً 8 أو 16، لذا فهي أقل تأثرًا.) يمكن منع ذلك عن طريق إزاحة نقطة تقسيم البحث الثنائي بحيث تقسم عند ^31/64 بدلاً من المنتصف تمامًا. ^[ 24 ^]

البحث الثنائي مقابل المخططات الأخرى

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

البحث الخطي

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

الأشجار

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

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

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

التجزئة

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

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

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

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

هياكل بيانات أخرى

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

الاختلافات

البحث الثنائي الموحد

يخزن البحث الثنائي الموحد، بدلاً من الحدود الدنيا والعليا، الفرق في فهرس العنصر الأوسط بين التكرار الحالي والتكرار التالي. ويتم حساب جدول بحث يحتوي على هذه الفروق مسبقًا. على سبيل المثال، إذا كانت المصفوفة المراد البحث فيها هي $[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$ بنفس المقدار. ^{[ 44 ]} لتقليل مساحة البحث، تضيف الخوارزمية هذا التغيير أو تطرحه من مؤشر العنصر الأوسط. قد يكون البحث الثنائي المنتظم أسرع على الأنظمة التي يصعب فيها حساب نقطة المنتصف، مثل الحواسيب العشرية . ^{[ 45 ]}

البحث الأسي

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

بحث الاستيفاء

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

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

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

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

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

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

التعميم على الرسوم البيانية

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

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

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

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

تقتصر الحواسيب التقليدية على أسوأ حالة من حالات الدقة التامة ${\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 }$ هو اللوغاريتم الطبيعي . ^{[ 58 ]} توجد خوارزمية بحث ثنائية كمومية دقيقة تعمل في ${\textstyle 4\log _{605}n\approx 0.433\log _{2}n}$ الاستعلامات في أسوأ الحالات. ^{[ 59 ]} بالمقارنة، تُعد خوارزمية غروفر الخوارزمية الكمومية المثلى للبحث في قائمة غير مرتبة من العناصر، وهي تتطلب $O({\sqrt {n}})$ استفسارات. ^{[ 60 ]}

تاريخ

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

في عام 1946، أشار جون موشلي لأول مرة إلى البحث الثنائي ضمن محاضرات مدرسة مور ، وهي دورة جامعية رائدة وأساسية في علوم الحاسوب. ^{[ 9 ]} وفي عام 1957، نشر ويليام ويسلي بيترسون أول طريقة للبحث بالاستيفاء. ^{[ 9 ]}^{[ 61 ]} كانت جميع خوارزميات البحث الثنائي المنشورة تعمل فقط مع المصفوفات التي يقل طولها عن قوة العدد اثنين بواحد ^{[ i ]} حتى عام 1960، عندما نشر ديريك هنري ليمر خوارزمية بحث ثنائي تعمل على جميع المصفوفات. ^{[ 63 ]} وفي عام 1962، قدم هيرمان بوتنبروش تطبيقًا للبحث الثنائي بلغة ALGOL 60 ، حيث وضع مقارنة التساوي في النهاية ، مما زاد متوسط عدد التكرارات بمقدار واحد، ولكنه قلل عدد المقارنات في كل تكرار إلى واحد. ^{[ ٨ ]} طُوِّر البحث الثنائي المنتظم بواسطة أ. ك. تشاندرا من جامعة ستانفورد عام ١٩٧١. ^{[ ٩ ]} في عام ١٩٨٦، قدّم برنارد شازيل وليونيداس ج. غيباس التتالي الكسري كطريقة لحل العديد من مسائل البحث في الهندسة الحسابية . ^{[ ٥٠ ]}^{[ ٦٤ ]}^{[ ٦٥ ]}

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

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

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

عندما كلف جون بنتلي طلابه بحل مسألة البحث الثنائي في دورة تدريبية للمبرمجين المحترفين، وجد أن تسعين بالمئة منهم فشلوا في تقديم حل صحيح بعد عدة ساعات من العمل عليه، ويعود السبب الرئيسي إلى فشل التطبيقات غير الصحيحة في التشغيل أو إعادتها إجابة خاطئة في حالات نادرة . ^{[ 66 ]} وأظهرت دراسة نُشرت عام 1988 أن الشفرة الصحيحة لهذه المسألة لا توجد إلا في خمسة كتب دراسية من أصل عشرين. ^{[ 67 ]} علاوة على ذلك، احتوى تطبيق بنتلي الخاص للبحث الثنائي، والمنشور في كتابه "لآلئ البرمجة" عام 1986 ، على خطأ تجاوز سعة ظل غير مكتشف لأكثر من عشرين عامًا. كما احتوت مكتبة لغة جافا البرمجية لتطبيق البحث الثنائي على نفس خطأ تجاوز السعة لأكثر من تسع سنوات. ^{[ 68 ]}

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

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

دعم المكتبة

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

توفر لغة C هذه الوظيفةbsearch() في مكتبتها القياسية ، والتي يتم تنفيذها عادةً عبر البحث الثنائي، على الرغم من أن المعيار الرسمي لا يشترط ذلك. ^{[ 71 ]}
توفر المكتبة القياسية للغة C++ الدوال binary_search()و lower_bound()و upper_bound(). ^[⁷²equal_range() ] وباستخدام مكتبة C++20 ^، يمكن تطبيقها على نطاق كما يلي .std::rangesstd::ranges::binary_search()
توفر مكتبة Phobos القياسية في لغة Dstd.range ، في الوحدة النمطية، نوعًا SortedRange(يتم إرجاعه بواسطة sort()الدوال assumeSorted()) مع طرق contains()، equalRange()و ، lowerBound()و trisect()، والتي تستخدم تقنيات البحث الثنائي افتراضيًا للنطاقات التي توفر وصولًا عشوائيًا. ^{[ 73 ]}
توفر لغة كوبولSEARCH ALL الفعل اللازم لإجراء عمليات البحث الثنائي على جداول كوبول المرتبة. ^{[ 74 ]}
تحتوي حزمة المكتبة القياسية للغة Gosort على الدوال التالية Search: و SearchInts، SearchFloat64sو ، و SearchStrings، والتي تُنفذ البحث الثنائي العام، بالإضافة إلى تطبيقات محددة للبحث في شرائح الأعداد الصحيحة، والأعداد العشرية، والسلاسل النصية، على التوالي. ^{[ 75 ]}
توفر لغة جافا مجموعة من الطرق الثابتة المحملة بشكل زائدbinarySearch() في الفئات Arraysوفي الحزمة Collectionsالقياسية java.utilلإجراء عمليات البحث الثنائي على مصفوفات جافا وعلى Lists، على التوالي. ^{[ 76 ]}^{[ 77 ]}
يُقدّم إطار عمل .NET 2.0 من مايكروسوفت إصدارات عامة ثابتة لخوارزمية البحث الثنائي في فئاته الأساسية للمجموعات. ومن الأمثلة على ذلك System.Arrayطريقة BinarySearch<T>(T[] array, T value). ^{[ 78 ]}
بالنسبة للغة Objective-C ، يوفر إطار عمل Cocoa هذه الطريقة في نظام التشغيل Mac OS X 10.6 والإصدارات الأحدث. ^[⁷⁹^] كما يحتوي إطار عمل Core Foundation C من Apple على دالة مماثلة. ^[⁸⁰^]NSArray-indexOfObject:inSortedRange:options:usingComparator:CFArrayBSearchValues()
توفر لغة بايثونbisect وحدةً تحافظ على ترتيب القائمة دون الحاجة إلى إعادة ترتيبها بعد كل عملية إدخال. ^{[ 81 ]}
تتضمن فئة Array في لغة Rubybsearch طريقةً تتضمن مطابقة تقريبية مدمجة. ^{[ 82 ]}
توفر أداة Rust 's slice primitive binary_search(), binary_search_by(), binary_search_by_key(), و partition_point(). ^{[ 83 ]}

انظر أيضاً

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

ملاحظات ومراجع

قُدِّمَت هذه المقالة إلى ويكي جورنال أوف ساينس للمراجعة الأكاديمية الخارجية من قِبَل النظراء في عام ٢٠١٨ ( تقارير المراجعين ). أُعيد دمج المحتوى المُحدَّث في صفحة ويكيبيديا بموجب ترخيص CC-BY-SA-3.0 ( ٢٠١٩ ). النسخة المُعتمدة بعد المراجعة هي: أنتوني لين وآخرون (٢ يوليو ٢٠١٩). "خوارزمية البحث الثنائي" (PDF) . ويكي جورنال أوف ساينس . ٢ (١): ٥. doi : 10.15347/WJS/2019.005 . ISSN 2470-6345 . Wikidata Q81434400 .

ملحوظات

↑ الـ $O$ هي صيغة Big O ، و $\log$ هو اللوغاريتم . في ترميز Big O، لا يهم أساس اللوغاريتم لأن كل لوغاريتم لأساس معين هو عامل ثابت للوغاريتم آخر لأساس آخر. أي، $\log _{b}(n)=\log _{k}(n)\div \log _{k}(b)$ ، أين $\log _{k}(b)$ ثابت.
↑ يمكن تمثيل أي خوارزمية بحث تعتمد فقط على المقارنات باستخدام شجرة مقارنة ثنائية. المسار الداخلي هو أي مسار من الجذر إلى عقدة موجودة. ليكن $I$ ليكن طول المسار الداخلي هو مجموع أطوال جميع المسارات الداخلية. إذا كان احتمال البحث عن كل عنصر متساوياً، فإن الحالة المتوسطة هي $1+{\frac {I}{n}}$ أو ببساطة، واحد زائد متوسط أطوال جميع المسارات الداخلية للشجرة. وذلك لأن المسارات الداخلية تمثل العناصر التي تقارنها خوارزمية البحث بالهدف. وتمثل أطوال هذه المسارات الداخلية عدد التكرارات بعد العقدة الجذرية. وبجمع متوسط هذه الأطوال مع التكرار الواحد عند الجذر، نحصل على الحالة المتوسطة. لذا، لتقليل متوسط عدد المقارنات، يجب أن يكون طول المسار الداخلي $I$ يجب تقليل طول المسار الداخلي. اتضح أن شجرة البحث الثنائي تُقلل طول المسار الداخلي. أثبت كنوت (1998) أن طول المسار الخارجي (طول المسار عبر جميع العقد التي يوجد بها كلا الفرعين لكل عقدة موجودة بالفعل) يكون في أدنى حد له عندما تقع العقد الخارجية (العقد التي ليس لها فروع) ضمن مستويين متتاليين من الشجرة. ينطبق هذا أيضًا على المسارات الداخلية، حيث يكون طول المسار الداخلي $I$ يرتبط خطيًا بطول المسار الخارجي $E$ لأي شجرة من $n$ العقد، $I=E-2n$ عندما تحتوي كل شجرة فرعية على عدد مماثل من العقد، أو بعبارة أخرى، عندما تُقسّم المصفوفة إلى نصفين في كل تكرار، فإن العقد الخارجية، بالإضافة إلى عقدها الأبوية الداخلية، تقع ضمن مستويين. ويترتب على ذلك أن البحث الثنائي يُقلل عدد المقارنات المتوسطة، لأن شجرة المقارنة الخاصة به تتميز بأقصر طول ممكن للمسار الداخلي. ^{[ 14 ]}
↑ أوضح كنوت في عام 1998 ، من خلال نموذج حاسوبه MIX الذي صممه كنوت كتمثيل لحاسوب عادي، أن متوسط وقت تشغيل هذا التباين لإجراء بحث ناجح هو ${\textstyle 17.5\log _{2}n+17}$ وحدات زمنية مقارنة بـ ${\textstyle 18\log _{2}n-16}$ وحدات للبحث الثنائي العادي. يزداد التعقيد الزمني لهذا النوع بشكل أبطأ قليلاً، ولكن على حساب زيادة التعقيد الأولي. ^{[ 18 ]}
أجرى كنوت عام 1998 تحليلًا رسميًا لأداء الوقت لكلا خوارزميتي البحث هاتين. على حاسوب MIX الخاص بكنوت ، والذي صممه كنوت كتمثيل لحاسوب عادي، يستغرق البحث الثنائي في المتوسط ${\textstyle 18\log n-16}$ وحدات زمنية للبحث الناجح، بينما يستغرق البحث الخطي مع عقدة حارس في نهاية القائمة ${\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}$ الوحدات. يتميز البحث الخطي بانخفاض تعقيده الأولي لأنه يتطلب الحد الأدنى من العمليات الحسابية، ولكنه سرعان ما يتفوق على البحث الثنائي من حيث التعقيد. على جهاز MIX، يتفوق البحث الثنائي على البحث الخطي باستخدام عنصر حارس فقط إذا ${\textstyle n>44}$ .^[14]^[27]
↑Inserting the values in sorted order or in an alternating lowest-highest key pattern will result in a binary search tree that maximizes the average and worst-case search time.^[32]
↑It is possible to search some hash table implementations in guaranteed constant time.^[37]
↑This is because simply setting all of the bits which the hash functions point to for a specific key can affect queries for other keys which have a common hash location for one or more of the functions.^[42]
↑There exist improvements of the Bloom filter which improve on its complexity or support deletion; for example, the cuckoo filter exploits cuckoo hashing to gain these advantages.^[42]
↑That is, arrays of length 1, 3, 7, 15, 31 ...^[62]

Citations

↑Williams, Jr., Louis F. (22 April 1976). A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference. ACM. pp. 95–101. doi:10.1145/503561.503582. Archived from the original on 12 March 2017. Retrieved 29 June 2018.
1 2Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search".
↑Butterfield & Ngondi 2016, p. 46.
↑Cormen et al. 2009, p. 39.
↑Weisstein, Eric W."Binary search". MathWorld.
1 2Flores, Ivan; Madpis, George (1 September 1971). "Average binary search length for dense ordered lists". Communications of the ACM. 14 (9): 602–603. doi:10.1145/362663.362752. ISSN 0001-0782. S2CID 43325465.
1 2 3Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
1 2 3 4 بوتنبروش، هيرمان (1 أبريل 1962). "بنية واستخدام ALGOL 60" . مجلة ACM . 9 (2): 161-221 . doi : 10.1145/321119.321120 . ISSN 0004-5411 . S2CID 13406983 . تم وصف الإجراء في الصفحة 214 (الفقرة 43)، بعنوان "برنامج البحث الثنائي".
1 2 3 4 5 6 Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، القسم الفرعي "التاريخ وقائمة المراجع".
1 2 كاساهارا وموريشيتا 2006 ، الصفحات من 8 إلى 9.
1 2 3 Sedgewick & Wayne 2011 ، §3.1 ، القسم الفرعي "الرتبة والاختيار".
1 2 3 Goldman & Goldman 2008 ، ص 461–463.
↑ Sedgewick & Wayne 2011 ، §3.1 ، القسم الفرعي "استعلامات النطاق".
1 2 3 4 5 6 7 8 9 10 11 12 Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب") ، القسم الفرعي "مزيد من التحليل للبحث الثنائي".
↑ Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، "النظرية ب".
↑ تشانغ 2003 ، ص 169.
1 2 3 Knuth 1997 ، §2.3.4.5 ("طول المسار").
1 2 Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، القسم الفرعي "التمرين 23".
↑ رولف، تيموثي ج. (1997). "الاشتقاق التحليلي للمقارنات في البحث الثنائي" . نشرة ACM SIGNUM . 32 (4): 15-19 . doi : 10.1145/289251.289255 . S2CID 23752485 .
↑ هيرف، مايكل (ديسمبر 2001). "حيل الجذر" . الرؤية المجسمة: رسومات .
↑ "تنفيذ دالة total_cmp لـ f32 و f64 بواسطة golddranks · طلب سحب رقم 72568 · rust-lang/rust" . GitHub .– يحتوي على اقتباسات ذات صلة من معيار IEEE 754-2008 و-2019. يحتوي على تطبيق وشرح لتورية لفظية.
↑ "البحث الثنائي *يزيل* التنبؤات الخاطئة للفروع - بول خونغ: بعض لغة ليسب" . pvk.ca .
↑ خونغ، بول-فيراك؛ مورين، بات (2017). "تخطيطات المصفوفات للبحث القائم على المقارنة". مجلة الخوارزميات التجريبية . 22. المقالة 1.3. arXiv : 1509.05053 . doi : 10.1145/3053370 . S2CID 23752485 .
↑ "البحث الثنائي حالة شاذة بالنسبة لذاكرة التخزين المؤقت - بول خونغ: بعض لغة ليسب" . pvk.ca .
↑ كنوت 1997 ، §2.2.2 ("التخصيص التسلسلي").
1 2 3 4 بيم، بول؛ فيش، فيث إي. (2001). "الحدود المثلى لمسألة السلف والمسائل ذات الصلة" . مجلة علوم الحاسوب والنظم . 65 (1): 38-72 . doi : 10.1006/jcss.2002.1822 .
↑ كنوت 1998 ، إجابات التمارين (§6.2.1) لـ "التمرين 5".
↑ كنوت 1998 ، §6.2.1 ("البحث في جدول مرتب").
↑ Knuth 1998 ، §5.3.1 ("الفرز بالمقارنة الدنيا").
↑ Sedgewick & Wayne 2011 , §3.2 ("جداول الرموز المرتبة").
↑ Sedgewick & Wayne 2011 , §3.2 ("أشجار البحث الثنائية"), القسم الفرعي "الأساليب القائمة على الترتيب والحذف".
↑ Knuth 1998 ، §6.2.2 ("البحث في الشجرة الثنائية")، القسم الفرعي "ولكن ماذا عن أسوأ الحالات؟".
↑ Sedgewick & Wayne 2011 ، §3.5 ("التطبيقات")، "أي تطبيق لجدول الرموز يجب أن أستخدمه؟".
↑ كنوت 1998 ، §5.4.9 ("الأقراص والطبول").
↑ كنوت 1998 ، §6.2.4 ("الأشجار متعددة الاتجاهات").
↑ كنوت 1998 ، §6.4 ("التجزئة").
↑ Knuth 1998 ، §6.4 ("التجزئة") ، القسم الفرعي "التاريخ".
^ ديتزفيلبينجر ، مارتن. الأماكن القريبة : الأماكن القريبة : ماير أوف دير هايد، فريدهيلم؛ روهنيرت، هانز. تارجان، روبرت إي. (أغسطس 1994). "التجزئة الديناميكية المثالية: الحدود العلوية والسفلية". مجلة SIAM للحوسبة . 23 (4): 738-761 . دوى : 10.1137 / S0097539791194094 .
↑ مورين، بات. "جداول التجزئة" (ملف PDF) . ص 1. مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022. تم الاطلاع عليه في 28 مارس 2016 .
↑ كنوت 2011 ، §7.1.3 ("الحيل والتقنيات المتعلقة بالبتات").
1 2 سيلفرشتاين، آلان، دليل ورشة عمل جودي الرابع (PDF) ، هيوليت-باكارد ، الصفحات 80-81 ، مؤرشف (PDF) من الأصل في 9 أكتوبر 2022
1 2 فان، بن؛ أندرسن، ديف جي؛ كامينسكي، مايكل؛ ميتزنماخر، مايكل دي. (2014). مرشح الوقواق: عمليًا أفضل من بلوم . وقائع المؤتمر الدولي العاشر لجمعية آلات الحوسبة حول تجارب وتقنيات الشبكات الناشئة. الصفحات 75-88 . doi : 10.1145/2674005.2674994 .
↑ بلوم، بيرتون هـ. (1970). "المفاضلات بين المساحة والوقت في ترميز التجزئة مع الأخطاء المسموح بها". اتصالات رابطة آلات الحوسبة . 13 (7): 422-426 . CiteSeerX 10.1.1.641.9096 . doi : 10.1145/362686.362692 . S2CID 7931252 .
↑ Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، القسم الفرعي "اختلاف مهم".
↑ Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، القسم الفرعي "الخوارزمية U".
↑ موفات وتوربين 2002 ، ص 33.
1 2 3 Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب") ، القسم الفرعي "بحث الاستيفاء".
↑ Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، القسم الفرعي "التمرين 22".
↑ بيرل، يهوشوا؛ إيتاي، ألون؛ أفني، حاييم (1978). "بحث الاستيفاء - بحث لوغاريتمي لوغاريتمي ن " . اتصالات رابطة آلات الحوسبة . 21 (7): 550-553 . doi : 10.1145/359545.359557 . S2CID 11089655 .
1 2 3 شازيل، برنارد ؛ ليو، دينغ (6 يوليو 2001). الحدود الدنيا للبحث عن التقاطع والتتالي الجزئي في الأبعاد العليا . المؤتمر الثالث والثلاثون لجمعية الحوسبة الآلية حول نظرية الحوسبة . جمعية الحوسبة الآلية. الصفحات 322-329 . doi : 10.1145/380752.380818 . ISBN 978-1-58113-349-3تم الاطلاع عليه بتاريخ 30 يونيو 2018 .
↑ شازيل، برنارد ؛ ليو، دينغ (1 مارس 2004). "الحدود الدنيا للبحث عن التقاطع والتتالي الجزئي في الأبعاد الأعلى" (ملف PDF) . مجلة علوم الحاسوب والأنظمة . 68 (2): 269-284 . CiteSeerX 10.1.1.298.7772 . doi : 10.1016/j.jcss.2003.07.003 . ISSN 0022-0000 . مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022. تم الاطلاع عليه في 30 يونيو 2018 .
↑ إمام جومه زاده، إحسان؛ كيمبي، ديفيد؛ سينغال، فيكرانت (2016). البحث الثنائي الحتمي والاحتمالي في الرسوم البيانية . المؤتمر الثامن والأربعون لجمعية الحوسبة الآلية حول نظرية الحوسبة . الصفحات 519-532 . arXiv : 1503.00805 . doi : 10.1145/2897518.2897656 .
↑ بن أور، مايكل؛ حسيديم، أفيناتان (2008). "المتعلم البايزي هو الأمثل للبحث الثنائي الضوضائي (وجيد جدًا للحوسبة الكمومية أيضًا)" (ملف PDF) . الندوة التاسعة والأربعون حول أسس علوم الحاسوب . الصفحات 221-230 . doi : 10.1109/FOCS.2008.58 . ISBN 978-0-7695-3436-7تمت أرشفة الملف (PDF) من النسخة الأصلية في 9 أكتوبر 2022.
↑ بيلك، أندريه (1989). "البحث باحتمالية خطأ معروفة" . علوم الحاسوب النظرية . 63 (2): 185-202 . doi : 10.1016/0304-3975(89)90077-7 .
↑ ريفست، رونالد ل .؛ ماير، ألبرت ر .؛ كليتمان، دانيال ج .؛ وينكلمان، ك. التعامل مع الأخطاء في إجراءات البحث الثنائي . المؤتمر العاشر لجمعية الحوسبة الآلية حول نظرية الحوسبة . doi : 10.1145/800133.804351 .
↑ بيلك، أندريه (2002). "ألعاب البحث مع الأخطاء - خمسون عامًا من التعامل مع الكاذبين" . علوم الحاسوب النظرية . 270 ( 1-2 ): 71-109 . doi : 10.1016/S0304-3975(01)00303-6 .
^ ريني ، ألفريد (1961). “حول مشكلة في نظرية المعلومات”. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei . 6 : 515 – 516. ن.ر 0143666 .
↑ هوير، بيتر؛ نيربيك، يان؛ شي، ياويون (2002). "التعقيدات الكمومية للبحث المرتب، والفرز، وتمييز العناصر". Algorithmica . 34 (4): 429–448 . arXiv : quant-ph/0102078 . doi : 10.1007/s00453-002-0976-3 . S2CID 13717616 .
↑ تشايلدز، أندرو م.؛ لانداهل، أندرو ج.؛ باريلو، بابلو أ. (2007). "خوارزميات الكم لمسألة البحث المرتب عبر البرمجة شبه المحددة". مجلة Physical Review A. 75 ( 3). 032335. arXiv : quant-ph/0608161 . Bibcode : 2007PhRvA..75c2335C . doi : 10.1103/PhysRevA.75.032335 . S2CID 41539957 .
↑ جروفر، لوف ك. (1996). خوارزمية ميكانيكية كمومية سريعة للبحث في قواعد البيانات . المؤتمر الثامن والعشرون لجمعية الحوسبة الآلية حول نظرية الحوسبة . فيلادلفيا، بنسلفانيا. الصفحات 212-219 . arXiv : quant-ph/9605043 . doi : 10.1145/237814.237866 .
↑ بيترسون، ويليام ويسلي (1957). "العنونة للتخزين ذي الوصول العشوائي". مجلة آي بي إم للبحوث والتطوير . 1 (2): 130-146 . doi : 10.1147/rd.12.0130 .
↑ "2^ن − 1". OEIS A000225 مؤرشف في 8 يونيو 2016 في Wayback Machine . تم الاسترجاع في 7 مايو 2016.
↑ ليمر، ديريك (1960). "تعليم الحاسوب حيلًا توافقية". التحليل التوافقي . وقائع ندوات في الرياضيات التطبيقية. المجلد 10. الصفحات 180-181 . doi : 10.1090/psapm/010/0113289 . ISBN 9780821813102MR 0113289 . {{cite book}}عدم توافق رقم ISBN / التاريخ ( مساعدة )
↑ شازيل، برنارد ؛ غيباس، ليونيداس ج. (1986). "التتالي الجزئي: الجزء الأول. تقنية لهيكلة البيانات" (ملف PDF) . Algorithmica . 1 ( 1-4 ): 133-162 . CiteSeerX 10.1.1.117.8349 . doi : 10.1007/BF01840440 . S2CID 12745042 .
↑ شازيل، برنارد ؛ غيباس، ليونيداس ج. (1986)، "التتالي الجزئي: الجزء الثاني. التطبيقات" (ملف PDF) ، Algorithmica ، 1 ( 1-4 ): 163-191 ، doi : 10.1007/BF01840441 ، S2CID 11232235
↑ بنتلي 2000 ، §4.1 ("تحدي البحث الثنائي").
↑ باتيس، ريتشارد إي. (1988). "أخطاء الكتب الدراسية في البحث الثنائي". نشرة SIGCSE . 20 : 190-194 . doi : 10.1145/52965.53012 .
↑ بلوخ، جوشوا (2 يونيو 2006). "خبر عاجل: جميع عمليات البحث الثنائي وفرز الدمج تقريبًا معيبة" . مدونة أبحاث جوجل . مؤرشف من الأصل في 1 أبريل 2016. تم الاطلاع عليه في 21 أبريل 2016 .
↑ روجيري، سالفاتوري (2003). "حول حساب نصف مجموع عددين صحيحين" (ملف PDF) . رسائل معالجة المعلومات . 87 (2): 67-71 . CiteSeerX 10.1.1.13.5631 . doi : 10.1016/S0020-0190(03)00263-1 . مؤرشف (ملف PDF) من الأصل في 3 يوليو 2006. تم الاطلاع عليه في 19 مارس 2016 .
↑ بنتلي 2000 ، §4.4 ("المبادئ").
↑ "bsearch – البحث الثنائي في جدول مُرتب" . المواصفات الأساسية لمجموعة Open Group ( الطبعة السابعة). مجموعة Open Group . 2013. مؤرشف من الأصل في 21 مارس 2016. تم الاطلاع عليه في 28 مارس 2016 .
↑ ستروستروب 2013 ، ص 945.
↑ "std.range - لغة البرمجة D" . dlang.org . تم الاطلاع عليه بتاريخ 29 أبريل 2020 .
↑ يونيسيس ( 2012)، دليل مرجعي لبرمجة COBOL ANSI-85 ، المجلد 1، الصفحات 598-601
↑ "فرز الحزم" . لغة البرمجة Go . مؤرشف من الأصل في 25 أبريل 2016. تم الاطلاع عليه في 28 أبريل 2016 .
↑ "java.util.Arrays" . وثائق Java Platform Standard Edition 8. شركة أوراكل . مؤرشف من الأصل في 29 أبريل 2016. تم الاطلاع عليه في 1 مايو 2016 .
↑ "java.util.Collections" . وثائق Java Platform Standard Edition 8. شركة أوراكل . مؤرشف من الأصل في 23 أبريل 2016. تم الاطلاع عليه في 1 مايو 2016 .
↑ "List<T>.BinarySearch method (T)" . شبكة مطوري مايكروسوفت . مؤرشف من الأصل في 7 مايو 2016. تم الاطلاع عليه في 10 أبريل 2016 .
↑ "NSArray" . مكتبة مطوري ماك . شركة آبل . مؤرشف من الأصل في 17 أبريل 2016. تم الاطلاع عليه في 1 مايو 2016 .
↑ "CFArray" . مكتبة مطوري ماك . شركة آبل . مؤرشف من الأصل في 20 أبريل 2016. تم الاطلاع عليه في 1 مايو 2016 .
↑ "8.6. bisect — خوارزمية تقسيم المصفوفة إلى نصفين" . مكتبة بايثون القياسية . مؤسسة برمجيات بايثون. مؤرشف من الأصل في 25 مارس 2018. تم الاطلاع عليه في 26 مارس 2018 .
↑ فيتزجيرالد 2015 ، ص 152.
↑ "النوع الأولي " . مكتبة Rust القياسية . مؤسسة Rust . 2024. تم الاطلاع عليه بتاريخ 25 مايو 2024 .slice

مصادر

بنتلي، جون (2000). لآلئ البرمجة ( الطبعة الثانية). أديسون-ويسلي . ISBN 978-0-201-65788-3.
باترفيلد، أندرو؛ نغوندي، جيرارد إي. (2016). قاموس علوم الحاسوب ( الطبعة السابعة). أكسفورد، المملكة المتحدة: مطبعة جامعة أكسفورد . ISBN 978-0-19-968897-5.
تشانغ، شي-كو (2003). هياكل البيانات والخوارزميات . هندسة البرمجيات وهندسة المعرفة. المجلد 13. سنغافورة: وورلد ساينتيفيك . ISBN 978-981-238-348-8.
كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009). مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN 978-0-262-03384-8.
فيتزجيرالد، مايكل (2015). مرجع روبي الجيب . سيباستوبول، كاليفورنيا: أورايلي ميديا . ISBN 978-1-4919-2601-7.
جولدمان، سالي أ .؛ جولدمان، كينيث ج. (2008). دليل عملي لهياكل البيانات والخوارزميات باستخدام جافا . بوكا راتون، فلوريدا: مطبعة سي آر سي . رقم ISBN 978-1-58488-455-2.
كاساهارا، ماساهيرو؛ موريشيتا، شينيتشي (2006). معالجة تسلسل الجينوم على نطاق واسع . لندن، المملكة المتحدة: مطبعة إمبريال كوليدج. ISBN 978-1-86094-635-6.
كنوت، دونالد (1997). الخوارزميات الأساسية . فن برمجة الحاسوب . المجلد 1 ( الطبعة الثالثة). ريدينغ، ماساتشوستس: أديسون-ويسلي بروفيشنال. ISBN 978-0-201-89683-1.
كنوت، دونالد (1998). الفرز والبحث . فن برمجة الحاسوب . المجلد 3 ( الطبعة الثانية). ريدينغ، ماساتشوستس: أديسون-ويسلي بروفيشنال. ISBN 978-0-201-89685-5.
كنوت، دونالد (2011). الخوارزميات التوافقية . فن برمجة الحاسوب . المجلد 4أ ( الطبعة الأولى). ريدينغ، ماساتشوستس: أديسون-ويسلي بروفيشنال. ISBN 978-0-201-03804-0.
موفات، أليستير؛ توربين، أندرو (2002). خوارزميات الضغط والترميز . هامبورغ، ألمانيا: دار نشر كلوير الأكاديمية. doi : 10.1007/978-1-4615-0935-6 . ISBN 978-0-7923-7668-2.
سيدجويك، روبرت ؛ واين، كيفن (2011). الخوارزميات ( الطبعة الرابعة). أبر سادل ريفر، نيو جيرسي: أديسون-ويسلي بروفيشنال. ISBN 978-0-321-57351-3.نسخة مختصرة للويب ؛ نسخة كتاب .
ستروستروب، بيارن (2013). لغة البرمجة سي++ ( الطبعة الرابعة). أبر سادل ريفر، نيو جيرسي: أديسون-ويسلي بروفيشنال. رقم ISBN 978-0-321-56384-2.

روابط خارجية

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

[6] الـ $O$ هي صيغة Big O ، و $\log$ هو اللوغاريتم . في ترميز Big O، لا يهم أساس اللوغاريتم لأن كل لوغاريتم لأساس معين هو عامل ثابت للوغاريتم آخر لأساس آخر. أي، $\log _{b}(n)=\log _{k}(n)\div \log _{k}(b)$ ، أين $\log _{k}(b)$ ثابت.

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

[21] أوضح كنوت في عام 1998 ، من خلال نموذج حاسوبه MIX الذي صممه كنوت كتمثيل لحاسوب عادي، أن متوسط وقت تشغيل هذا التباين لإجراء بحث ناجح هو ${\textstyle 17.5\log _{2}n+17}$ وحدات زمنية مقارنة بـ ${\textstyle 18\log _{2}n-16}$ وحدات للبحث الثنائي العادي. يزداد التعقيد الزمني لهذا النوع بشكل أبطأ قليلاً، ولكن على حساب زيادة التعقيد الأولي. ^{[ 18 ]}

[31] أجرى كنوت عام 1998 تحليلًا رسميًا لأداء الوقت لكلا خوارزميتي البحث هاتين. على حاسوب MIX الخاص بكنوت ، والذي صممه كنوت كتمثيل لحاسوب عادي، يستغرق البحث الثنائي في المتوسط ${\textstyle 18\log n-16}$ وحدات زمنية للبحث الناجح، بينما يستغرق البحث الخطي مع عقدة حارس في نهاية القائمة ${\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}$ الوحدات. يتميز البحث الخطي بانخفاض تعقيده الأولي لأنه يتطلب الحد الأدنى من العمليات الحسابية، ولكنه سرعان ما يتفوق على البحث الثنائي من حيث التعقيد. على جهاز MIX، يتفوق البحث الثنائي على البحث الخطي باستخدام عنصر حارس فقط إذا ${\textstyle n>44}$ .^[14]^[27]

[37] Inserting the values in sorted order or in an alternating lowest-highest key pattern will result in a binary search tree that maximizes the average and worst-case search time.^[32]

[43] It is possible to search some hash table implementations in guaranteed constant time.^[37]

[49] This is because simply setting all of the bits which the hash functions point to for a specific key can affect queries for other keys which have a common hash location for one or more of the functions.^[42]

[50] There exist improvements of the Bloom filter which improve on its complexity or support deletion; for example, the cuckoo filter exploits cuckoo hashing to gain these advantages.^[42]

[71] That is, arrays of length 1, 3, 7, 15, 31 ...^[62]

[Williams1976-1] Williams, Jr., Louis F. (22 April 1976). A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference. ACM. pp. 95–101. doi:10.1145/503561.503582. Archived from the original on 12 March 2017. Retrieved 29 June 2018.

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Binary_search"-2] 1 2Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search".

[FOOTNOTEButterfieldNgondi201646-3] Butterfield & Ngondi 2016, p. 46.

[FOOTNOTECormenLeisersonRivestStein200939-4] Cormen et al. 2009, p. 39.

[5] Weisstein, Eric W."Binary search". MathWorld.

[FloresMadpis1971-7] 1 2Flores, Ivan; Madpis, George (1 September 1971). "Average binary search length for dense ordered lists". Communications of the ACM. 14 (9): 602–603. doi:10.1145/362663.362752. ISSN 0001-0782. S2CID 43325465.

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Algorithm_B"-8] 1 2 3Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".

[Bottenbruch1962-9] 1 2 3 4 بوتنبروش، هيرمان (1 أبريل 1962). "بنية واستخدام ALGOL 60" . مجلة ACM . 9 (2): 161-221 . doi : 10.1145/321119.321120 . ISSN 0004-5411 . S2CID 13406983 . تم وصف الإجراء في الصفحة 214 (الفقرة 43)، بعنوان "برنامج البحث الثنائي".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"History_and_bibliography"-10] 1 2 3 4 5 6 Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، القسم الفرعي "التاريخ وقائمة المراجع".

[FOOTNOTEKasaharaMorishita20068–9-11] 1 2 كاساهارا وموريشيتا 2006 ، الصفحات من 8 إلى 9.

[FOOTNOTESedgewickWayne2011§3.1,_subsection_"Rank_and_selection"-12] 1 2 3 Sedgewick & Wayne 2011 ، §3.1 ، القسم الفرعي "الرتبة والاختيار".

[FOOTNOTEGoldmanGoldman2008461–463-13] 1 2 3 Goldman & Goldman 2008 ، ص 461–463.

[FOOTNOTESedgewickWayne2011§3.1,_subsection_"Range_queries"-14] Sedgewick & Wayne 2011 ، §3.1 ، القسم الفرعي "استعلامات النطاق".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Further_analysis_of_binary_search"-15] 1 2 3 4 5 6 7 8 9 10 11 12 Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب") ، القسم الفرعي "مزيد من التحليل للبحث الثنائي".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_"Theorem_B"-16] Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، "النظرية ب".

[FOOTNOTEChang2003169-17] تشانغ 2003 ، ص 169.

[FOOTNOTEKnuth1997§2.3.4.5_("Path_length")-19] 1 2 3 Knuth 1997 ، §2.3.4.5 ("طول المسار").

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Exercise_23"-20] 1 2 Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، القسم الفرعي "التمرين 23".

[22] رولف، تيموثي ج. (1997). "الاشتقاق التحليلي للمقارنات في البحث الثنائي" . نشرة ACM SIGNUM . 32 (4): 15-19 . doi : 10.1145/289251.289255 . S2CID 23752485 .

[Herf_2001-23] هيرف، مايكل (ديسمبر 2001). "حيل الجذر" . الرؤية المجسمة: رسومات .

[rust_total_cmp-24] "تنفيذ دالة total_cmp لـ f32 و f64 بواسطة golddranks · طلب سحب رقم 72568 · rust-lang/rust" . GitHub .– يحتوي على اقتباسات ذات صلة من معيار IEEE 754-2008 و-2019. يحتوي على تطبيق وشرح لتورية لفظية.

[25] "البحث الثنائي *يزيل* التنبؤات الخاطئة للفروع - بول خونغ: بعض لغة ليسب" . pvk.ca .

[26] خونغ، بول-فيراك؛ مورين، بات (2017). "تخطيطات المصفوفات للبحث القائم على المقارنة". مجلة الخوارزميات التجريبية . 22. المقالة 1.3. arXiv : 1509.05053 . doi : 10.1145/3053370 . S2CID 23752485 .

[27] "البحث الثنائي حالة شاذة بالنسبة لذاكرة التخزين المؤقت - بول خونغ: بعض لغة ليسب" . pvk.ca .

[FOOTNOTEKnuth1997§2.2.2_("Sequential_Allocation")-28] كنوت 1997 ، §2.2.2 ("التخصيص التسلسلي").

[pred-29] 1 2 3 4 بيم، بول؛ فيش، فيث إي. (2001). "الحدود المثلى لمسألة السلف والمسائل ذات الصلة" . مجلة علوم الحاسوب والنظم . 65 (1): 38-72 . doi : 10.1006/jcss.2002.1822 .

[FOOTNOTEKnuth1998Answers_to_Exercises_(§6.2.1)_for_"Exercise_5"-30] كنوت 1998 ، إجابات التمارين (§6.2.1) لـ "التمرين 5".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table")-32] كنوت 1998 ، §6.2.1 ("البحث في جدول مرتب").

[FOOTNOTEKnuth1998§5.3.1_("Minimum-Comparison_sorting")-33] Knuth 1998 ، §5.3.1 ("الفرز بالمقارنة الدنيا").

[FOOTNOTESedgewickWayne2011§3.2_("Ordered_symbol_tables")-34] Sedgewick & Wayne 2011 , §3.2 ("جداول الرموز المرتبة").

[FOOTNOTESedgewickWayne2011§3.2_("Binary_Search_Trees"),_subsection_"Order-based_methods_and_deletion"-35] Sedgewick & Wayne 2011 , §3.2 ("أشجار البحث الثنائية"), القسم الفرعي "الأساليب القائمة على الترتيب والحذف".

[FOOTNOTEKnuth1998§6.2.2_("Binary_tree_searching"),_subsection_"But_what_about_the_worst_case?"-36] Knuth 1998 ، §6.2.2 ("البحث في الشجرة الثنائية")، القسم الفرعي "ولكن ماذا عن أسوأ الحالات؟".

[FOOTNOTESedgewickWayne2011§3.5_("Applications"),_"Which_symbol-table_implementation_should_I_use?"-38] Sedgewick & Wayne 2011 ، §3.5 ("التطبيقات")، "أي تطبيق لجدول الرموز يجب أن أستخدمه؟".

[FOOTNOTEKnuth1998§5.4.9_("Disks_and_Drums")-39] كنوت 1998 ، §5.4.9 ("الأقراص والطبول").

[FOOTNOTEKnuth1998§6.2.4_("Multiway_trees")-40] كنوت 1998 ، §6.2.4 ("الأشجار متعددة الاتجاهات").

[FOOTNOTEKnuth1998§6.4_("Hashing")-41] كنوت 1998 ، §6.4 ("التجزئة").

[FOOTNOTEKnuth1998§6.4_("Hashing"),_subsection_"History"-42] Knuth 1998 ، §6.4 ("التجزئة") ، القسم الفرعي "التاريخ".

[44] ديتزفيلبينجر ، مارتن. الأماكن القريبة : الأماكن القريبة : ماير أوف دير هايد، فريدهيلم؛ روهنيرت، هانز. تارجان، روبرت إي. (أغسطس 1994). "التجزئة الديناميكية المثالية: الحدود العلوية والسفلية". مجلة SIAM للحوسبة . 23 (4): 738-761 . دوى : 10.1137 / S0097539791194094 .

[45] مورين، بات. "جداول التجزئة" (ملف PDF) . ص 1. مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022. تم الاطلاع عليه في 28 مارس 2016 .

[FOOTNOTEKnuth2011§7.1.3_("Bitwise_Tricks_and_Techniques")-46] كنوت 2011 ، §7.1.3 ("الحيل والتقنيات المتعلقة بالبتات").

[judyarray-47] 1 2 سيلفرشتاين، آلان، دليل ورشة عمل جودي الرابع (PDF) ، هيوليت-باكارد ، الصفحات 80-81 ، مؤرشف (PDF) من الأصل في 9 أكتوبر 2022

[cuckoofilter-48] 1 2 فان، بن؛ أندرسن، ديف جي؛ كامينسكي، مايكل؛ ميتزنماخر، مايكل دي. (2014). مرشح الوقواق: عمليًا أفضل من بلوم . وقائع المؤتمر الدولي العاشر لجمعية آلات الحوسبة حول تجارب وتقنيات الشبكات الناشئة. الصفحات 75-88 . doi : 10.1145/2674005.2674994 .

[51] بلوم، بيرتون هـ. (1970). "المفاضلات بين المساحة والوقت في ترميز التجزئة مع الأخطاء المسموح بها". اتصالات رابطة آلات الحوسبة . 13 (7): 422-426 . CiteSeerX 10.1.1.641.9096 . doi : 10.1145/362686.362692 . S2CID 7931252 .

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"An_important_variation"-52] Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، القسم الفرعي "اختلاف مهم".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Algorithm_U"-53] Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، القسم الفرعي "الخوارزمية U".

[FOOTNOTEMoffatTurpin200233-54] موفات وتوربين 2002 ، ص 33.

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Interpolation_search"-55] 1 2 3 Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب") ، القسم الفرعي "بحث الاستيفاء".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Exercise_22"-56] Knuth 1998 ، §6.2.1 ("البحث في جدول مرتب")، القسم الفرعي "التمرين 22".

[57] بيرل، يهوشوا؛ إيتاي، ألون؛ أفني، حاييم (1978). "بحث الاستيفاء - بحث لوغاريتمي لوغاريتمي ن " . اتصالات رابطة آلات الحوسبة . 21 (7): 550-553 . doi : 10.1145/359545.359557 . S2CID 11089655 .

[ChazelleLiu2001-58] 1 2 3 شازيل، برنارد ؛ ليو، دينغ (6 يوليو 2001). الحدود الدنيا للبحث عن التقاطع والتتالي الجزئي في الأبعاد العليا . المؤتمر الثالث والثلاثون لجمعية الحوسبة الآلية حول نظرية الحوسبة . جمعية الحوسبة الآلية. الصفحات 322-329 . doi : 10.1145/380752.380818 . ISBN 978-1-58113-349-3تم الاطلاع عليه بتاريخ 30 يونيو 2018 .

[ChazelleLiu2004-59] شازيل، برنارد ؛ ليو، دينغ (1 مارس 2004). "الحدود الدنيا للبحث عن التقاطع والتتالي الجزئي في الأبعاد الأعلى" (ملف PDF) . مجلة علوم الحاسوب والأنظمة . 68 (2): 269-284 . CiteSeerX 10.1.1.298.7772 . doi : 10.1016/j.jcss.2003.07.003 . ISSN 0022-0000 . مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022. تم الاطلاع عليه في 30 يونيو 2018 .

[60] إمام جومه زاده، إحسان؛ كيمبي، ديفيد؛ سينغال، فيكرانت (2016). البحث الثنائي الحتمي والاحتمالي في الرسوم البيانية . المؤتمر الثامن والأربعون لجمعية الحوسبة الآلية حول نظرية الحوسبة . الصفحات 519-532 . arXiv : 1503.00805 . doi : 10.1145/2897518.2897656 .

[61] بن أور، مايكل؛ حسيديم، أفيناتان (2008). "المتعلم البايزي هو الأمثل للبحث الثنائي الضوضائي (وجيد جدًا للحوسبة الكمومية أيضًا)" (ملف PDF) . الندوة التاسعة والأربعون حول أسس علوم الحاسوب . الصفحات 221-230 . doi : 10.1109/FOCS.2008.58 . ISBN 978-0-7695-3436-7تمت أرشفة الملف (PDF) من النسخة الأصلية في 9 أكتوبر 2022.

[pelc1989-62] بيلك، أندريه (1989). "البحث باحتمالية خطأ معروفة" . علوم الحاسوب النظرية . 63 (2): 185-202 . doi : 10.1016/0304-3975(89)90077-7 .

[63] ريفست، رونالد ل .؛ ماير، ألبرت ر .؛ كليتمان، دانيال ج .؛ وينكلمان، ك. التعامل مع الأخطاء في إجراءات البحث الثنائي . المؤتمر العاشر لجمعية الحوسبة الآلية حول نظرية الحوسبة . doi : 10.1145/800133.804351 .

[64] بيلك، أندريه (2002). "ألعاب البحث مع الأخطاء - خمسون عامًا من التعامل مع الكاذبين" . علوم الحاسوب النظرية . 270 ( 1-2 ): 71-109 . doi : 10.1016/S0304-3975(01)00303-6 .

[65] ريني ، ألفريد (1961). “حول مشكلة في نظرية المعلومات”. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei . 6 : 515 – 516. ن.ر 0143666 .

[66] هوير، بيتر؛ نيربيك، يان؛ شي، ياويون (2002). "التعقيدات الكمومية للبحث المرتب، والفرز، وتمييز العناصر". Algorithmica . 34 (4): 429–448 . arXiv : quant-ph/0102078 . doi : 10.1007/s00453-002-0976-3 . S2CID 13717616 .

[quantumalgo-67] تشايلدز، أندرو م.؛ لانداهل، أندرو ج.؛ باريلو، بابلو أ. (2007). "خوارزميات الكم لمسألة البحث المرتب عبر البرمجة شبه المحددة". مجلة Physical Review A. 75 ( 3). 032335. arXiv : quant-ph/0608161 . Bibcode : 2007PhRvA..75c2335C . doi : 10.1103/PhysRevA.75.032335 . S2CID 41539957 .

[68] جروفر، لوف ك. (1996). خوارزمية ميكانيكية كمومية سريعة للبحث في قواعد البيانات . المؤتمر الثامن والعشرون لجمعية الحوسبة الآلية حول نظرية الحوسبة . فيلادلفيا، بنسلفانيا. الصفحات 212-219 . arXiv : quant-ph/9605043 . doi : 10.1145/237814.237866 .

[69] بيترسون، ويليام ويسلي (1957). "العنونة للتخزين ذي الوصول العشوائي". مجلة آي بي إم للبحوث والتطوير . 1 (2): 130-146 . doi : 10.1147/rd.12.0130 .

[70] "2^ن − 1". OEIS A000225 مؤرشف في 8 يونيو 2016 في Wayback Machine . تم الاسترجاع في 7 مايو 2016.

[72] ليمر، ديريك (1960). "تعليم الحاسوب حيلًا توافقية". التحليل التوافقي . وقائع ندوات في الرياضيات التطبيقية. المجلد 10. الصفحات 180-181 . doi : 10.1090/psapm/010/0113289 . ISBN 9780821813102MR 0113289 . {{cite book}}عدم توافق رقم ISBN / التاريخ ( مساعدة )

[73] شازيل، برنارد ؛ غيباس، ليونيداس ج. (1986). "التتالي الجزئي: الجزء الأول. تقنية لهيكلة البيانات" (ملف PDF) . Algorithmica . 1 ( 1-4 ): 133-162 . CiteSeerX 10.1.1.117.8349 . doi : 10.1007/BF01840440 . S2CID 12745042 .

[74] شازيل، برنارد ؛ غيباس، ليونيداس ج. (1986)، "التتالي الجزئي: الجزء الثاني. التطبيقات" (ملف PDF) ، Algorithmica ، 1 ( 1-4 ): 163-191 ، doi : 10.1007/BF01840441 ، S2CID 11232235

[FOOTNOTEBentley2000§4.1_("The_Challenge_of_Binary_Search")-75] بنتلي 2000 ، §4.1 ("تحدي البحث الثنائي").

[textbook-76] باتيس، ريتشارد إي. (1988). "أخطاء الكتب الدراسية في البحث الثنائي". نشرة SIGCSE . 20 : 190-194 . doi : 10.1145/52965.53012 .

[77] بلوخ، جوشوا (2 يونيو 2006). "خبر عاجل: جميع عمليات البحث الثنائي وفرز الدمج تقريبًا معيبة" . مدونة أبحاث جوجل . مؤرشف من الأصل في 1 أبريل 2016. تم الاطلاع عليه في 21 أبريل 2016 .

[semisum-78] روجيري، سالفاتوري (2003). "حول حساب نصف مجموع عددين صحيحين" (ملف PDF) . رسائل معالجة المعلومات . 87 (2): 67-71 . CiteSeerX 10.1.1.13.5631 . doi : 10.1016/S0020-0190(03)00263-1 . مؤرشف (ملف PDF) من الأصل في 3 يوليو 2006. تم الاطلاع عليه في 19 مارس 2016 .

[FOOTNOTEBentley2000§4.4_("Principles")-79] بنتلي 2000 ، §4.4 ("المبادئ").

[80] "bsearch – البحث الثنائي في جدول مُرتب" . المواصفات الأساسية لمجموعة Open Group ( الطبعة السابعة). مجموعة Open Group . 2013. مؤرشف من الأصل في 21 مارس 2016. تم الاطلاع عليه في 28 مارس 2016 .

[FOOTNOTEStroustrup2013945-81] ستروستروب 2013 ، ص 945.

[82] "std.range - لغة البرمجة D" . dlang.org . تم الاطلاع عليه بتاريخ 29 أبريل 2020 .

[83] يونيسيس ( 2012)، دليل مرجعي لبرمجة COBOL ANSI-85 ، المجلد 1، الصفحات 598-601

[84] "فرز الحزم" . لغة البرمجة Go . مؤرشف من الأصل في 25 أبريل 2016. تم الاطلاع عليه في 28 أبريل 2016 .

[85] "java.util.Arrays" . وثائق Java Platform Standard Edition 8. شركة أوراكل . مؤرشف من الأصل في 29 أبريل 2016. تم الاطلاع عليه في 1 مايو 2016 .

[86] "java.util.Collections" . وثائق Java Platform Standard Edition 8. شركة أوراكل . مؤرشف من الأصل في 23 أبريل 2016. تم الاطلاع عليه في 1 مايو 2016 .

[87] "List<T>.BinarySearch method (T)" . شبكة مطوري مايكروسوفت . مؤرشف من الأصل في 7 مايو 2016. تم الاطلاع عليه في 10 أبريل 2016 .

[88] "NSArray" . مكتبة مطوري ماك . شركة آبل . مؤرشف من الأصل في 17 أبريل 2016. تم الاطلاع عليه في 1 مايو 2016 .

[89] "CFArray" . مكتبة مطوري ماك . شركة آبل . مؤرشف من الأصل في 20 أبريل 2016. تم الاطلاع عليه في 1 مايو 2016 .

[90] "8.6. bisect — خوارزمية تقسيم المصفوفة إلى نصفين" . مكتبة بايثون القياسية . مؤسسة برمجيات بايثون. مؤرشف من الأصل في 25 مارس 2018. تم الاطلاع عليه في 26 مارس 2018 .

[FOOTNOTEFitzgerald2015152-91] فيتزجيرالد 2015 ، ص 152.

[92] "النوع الأولي " . مكتبة Rust القياسية . مؤسسة Rust . 2024. تم الاطلاع عليه بتاريخ 25 مايو 2024 .slice

[ 1 ]

2 ] أو

3

، خوارزمية بحث تُستخدم لإيجاد موقع قيمة مُستهدفة ضمن مصفوفة مُرتبة [4] [

البحث

[ أ ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

12

[ 13 ]

[ 14 ]

[

[ 16 ]

[ ب ]

[ 17 ]

ج

[

[

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

31/64

[ 25 ]

[ 26 ]

[ د ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ هـ ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ f ]

[ 38 ]

[ 39 ]

[

ذات

[ g ]

[ h ]

[ 43 ]

[ 44 ]

[ 45 ]

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

[ 55 ]

[ 56 ]

[ 57 ]

[ 58 ]

[ 59 ]

[ 60 ]

[ 61 ]

[ i ]

[ 63 ]

[ ٦٤ ]

[ ٦٥ ]

[ 66 ]

[ 67 ]

[ 68 ]

69

[ 70 ]

[ 71 ]

[

[ 73 ]

[ 74 ]

[ 75 ]

[ 76 ]

[ 77 ]

[ 78 ]

[

[

[ 81 ]

[ 82 ]

[ 83 ]

[27]

[32]

[37]

[42]

[62]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗