books working algorithm
If you do not find what you're looking for, you can use more accurate words.
خوارزمية العمل (Info)
الإجراءات
يعمل البحث الثنائي على المصفوفات المرتبة بهدف إيجاد موقع قيمة ما تُسمَّى القيمة المُستهدَفة أو القيمة الهدف. تبدأ العملية بمقارنة قيمة العنصر الموجود في منتصف المصفوفة بالقيمة المُستهدَفة، فإذا كانت هذه القيمة مُطابِقة لقيمة لعنصر، تُرجَع مرتبة العنصر في المصفوفة، وينتهي البحث. أَمَّا إذا كانت القيمة المُستهدَفة أقل من قيمة العنصر، فإن البحث سيستمر في النصف السفلي من المصفوفة. وأَمَّا إذا كانت القيمة المُستهدَفة أَصغر من قيمة العنصر، فإن البحث سيستمر في النصف العلوي من المصفوفة. يُحدد العنصر الموجود في منتصف نصف المصفوفة، وتعاد العملية السابقة حتى الوصول إلى القيمة المُستهدَفة أو انتهاء البحث دونَ ذلك، ويُقال عندها أن البحث غير ناجح أو أنه فَشِل في إيجاد القيمة المستهدفة في المصفوفة. في كل تكرار، تستبعد الخوارزمية النصف الذي لا يمكن أن توجد فيه القيمة المُستهدَفة.
الإجراء الرئيس
إذا كانت مصفوفةً تحتوي على عنصر أو سجل هي: مرتبة بالشكل التالي: ، وإذا كانت القيمة المُستهدَفة هي ، فبالإمكان العثور على مرتبة القيمة المُستهدَفة في المصفوفة ، أي إنجاز بحثٍ ثُنائيّ، باستخدم الخوارزمية التالية:
- و هما متحولان،(2) اضبط قيمة إلى وقيمة إلى .
- إذا كانت المُتراجِحة ، البحث غير ناجح، نهاية.
- هو متحوِّل يُمثِّل قيمة موقع العنصر المتوسط، اضبط قيمته إلى قيمة الجزء الصحيح المَحسُوب بالعلاقة ، أي أن هو أكبر عدد صحيح أصغر أو يساوي القيمة .
- هو متحول يمثل قيمة العنصر الذي مرتبته في المصفوفة :
- إذا كانت المُتراجِحة مُحققة، اضبط قيمة إلى ، ثُمَّ انتقل إلى الخطوة 2.
- إذا كانت المتراجحة مُحققة، اضبط قيمة إلى ، ثُمَّّ انتقل إلى الخطوة 2.
- وإلا، فإنَّ المساواة محققة، أرجع قيمة ، نهاية.
يتتبع هذا الإجراء التكراري حدود البحث باستخدام المتغيرين و اللّذين يُمثِّلان دائماً الحدين الأسفل والأعلى على الترتيب لجزء المصفوفة الذي تُطبَّق خوارزمية البحث الثنائي عليه. يمكن أيضاً التعبير عن الخوارزمية السابقة بالشيفرة التقريبية التالية، حيث تبقى أسماء وأنواع المتغيرات كما هي أعلاه، ويُمثِّل floor دالة الجزء الصحيح، وتشير الكلمة unsuccessful إلى قيمة رقمية محددة تُعبِّر عن فشل البحث.
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 بدالة الجزء الصحيح المُطبَّقة على القيمة . ولكن هذا قد يؤدي إلى إعطاء نتيجة مُغايرة إذا وجدت القيمة المُستهدَفة أكثر من مرة في المصفوفة.
إجراء بديل
في الإجراء الرئيس، ينجح البحث إذا كانت قيمة العنصر المتوسط تساوي القيمة المُستهدَفة ( ) في كل تكرار. تتخلى بعض تنفيذات الخوارزمية عن إجراء هذا الفحص أثناء كل تكرار، ولا تنفّذه إلا عند بقاء عنصر واحد فقط، أي عندما يكون . ينتج عن هذا التغيير حلقة مقارنة أسرع بسبب استبعاد إجراء عملية المقارنة مرةً واحدةً عند كل تكرار. ولكن هذه الطريقة تتطلب إجراء تكرارٍ إضافي واحد في المتوسط.
نشر هيرمان بوتينبروش أول تنفيذ للخوارزمية يتخلى عن إجراء فحص المساواة بالشكل السابق في عام 1962م.
- اضبط قيمة إلى وقيمة إلى .
- طالما ما يزال الشرط مُتحققاً:
- اضبط قيمة إلى قيمة المتمم الصحيح الأعلى المحسوب بالعلاقة ، وهو أصغر عدد صحيح يكون أكبر أو يساوي القيمة .
- إذا كانت المتراجحة متحققة، اضبط قيمة إلى .
- وإلا، أي عندما يتحقق ، اضبط قيمة إلى .
- الآن، افحص المساواة ، إذا كان الشرط متحققاً، أَرجِع ، نهاية. وإلا، بحث غير ناجح، نهاية.
يمكن أيضاً التعبير عن الخوارزمية السابقة باستعمال الشيفرة التقريبية التالية:
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
التعامل مع العناصر المكررة
قد يُرجِع الإجراء مرتبة أي عنصر تكون قيمته مساويةً للقيمة المستهدفة، حتى ولو كان هناك عناصر مُكرَرة في المصفوفة. على سبيل المثال، إذا كانت المصفوفة التي يُراد البحث فيها هي: وكانت القيمة المستهدفة هي ، فإن الخوارزمية سُترجع العنصر الرابع، أي الذي تكون قيمة مرتبته 3، والخامس، أي الذي تكون قيمة مرتبته 4. سيعيد الإجراء الرئيس العنصر الرابع فقط في هذه الحالة. في بعض الأحيان، يكون من الضروري العثور على موقع العنصر الموجود في أقصى اليسار أو العنصر الموجود في أقصى اليمين ضمن مجموعة العناصر المكررة في المصفوفة. في المثال أعلاه، ومن أجل العناصر المكررة التي تكون قيمتها 4، فإنَّ العنصر الرابع هو العنصر الموجود في أقصى اليسار، في حين أن العنصر الخامس هو العنصر الموجود في أقصى اليمين. في الإجراء البديل، إذا وجدت مجموعة من العناصر المُكررة، فإن مرتبة العنصر الموجود في أقصى اليمين سيعاد دائماً.
إجراء لإرجاع العنصر الموجود في أقصى اليسار
إذا كانت المصفوفة المُرتبة تحتوي على مجموعة من العناصر مكررة عددها ، يمكن استعمال الخوارزمية التالية لإرجاع العنصر الموجود في أقصى يسار مجموعة العناصر المرتبة:
- اضبط قيمة إلى وقيمة إلى .
- طالما كانت المتراجحة محققة:
- اضبط موقع العنصر الأوسط إلى قيمة الجزء الصحيح، أي: ، وهو أكبر عدد صحيح ذي قيمة أصغر أو تساوي .
- إذا كانت المتراجحة محققة، اضبط قيمة إلى .
- وإلا، أي عندما تكون المتراجحة محققة، اضبط قيمة إلى .
- أرجِع قيمة .
إذا كانت المتراجحة والشرط مُحققان، فإن هو العنصر الموجود في أقصى يسار مجموعة العناصر التي تساوي قيمة كل منها القيمة المستهدفة . حتى وإن كانت القيمة المُستهدفة غير موجودة في المصفوفة، فإن قيمة ، الناتجة عن تنفيذ الإجراء، ستمثل مرتبة القيمة المُستهدفة التي يجب أن تكون فيها، لو وجدت في المصفوفة، أو عدد عناصر المصفوفة التي كانت ستوجد قبل العنصر المُحدد بالقيمة المستهدفة.
يمكن أيضاً التعبير عن الخوارزمية السابقة بالشيفرة التقريبية التالية:
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
إجراء لإرجاع العنصر الموجود في أقصى اليمين
إذا كانت المصفوفة المُرتبة تحتوي على مجموعة متكررة من العناصر عددها ، يمكن استعمال الخوارزمية التالية لإرجاع العنصر الموجود في أقصى يمين مجموعة العناصر المرتبة:
- اضبط قيمة إلى وقيمة إلى .
- طالما كانت المتراجحة متحققة:
- اضبط موقع العنصر الأوسط إلى قيمة الجزء الصحيح، أي: ، وهو أكبر عدد صحيح ذو قيمة أقل أو تساوي .
- إذا كانت المتراجحة متحققة، اضبط قيمة إلى .
- وإلا، أي عندما تكون المتراجحة متحققة، اضبط قيمة إلى .
- أرجع قيمة .
إذا كانت المتراجحة والشرط مُتحققان، فإن هو العنصر الموجود في أقصى يمين مجموعة العناصر التي تساوي قيمة كل منها القيمة المستهدفة . حتى وإن كانت القيمة المُستهدفة غير موجودة في المصفوفة، فإن قيمة ، الناتجة عن تنفيذ الإجراء، ستمثِّل عدد عناصر المصفوفة التي كانت ستوجد بعد العنصر المُحدد بالقيمة المستهدفة، لو وُجِدَ.
يمكن أيضاً التعبير عن الخوارزمية السابقة بالشيفرة التقريبية التالية:
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
تطابقات تقريبية
تبحث الإجراءات السابقة عن التطابقات التامة بين القيمة المستهدفة وعناصر المصفوفة المُرَتَّبة، ثُمَّ تعيد موضع العنصر المتطابق في المصفوفة. وعلى أي حال، يمكن توسيع البحث الثنائي ليشمل البحث عن تطابقات تقريبية اعتماداً على فكرة أن البحث الثنائي يعمل على المصفوفات المُرتبة. على سبيل المثال، من أجل قيمة مستهدفة ما غير موجودة في المصوفة، يُمكن استخدام البحث الثنائي لحساب مرتبة القيمة، أي عدد عناصر المصفوفة ذوات القيم الأصغر منها، والمرتبة السابقة لها، أي مرتبة العنصر السابق الأصغر، والمرتبة اللاحقة لها، أي مرتبة العنصر التالي الأكبر، والجار الأقرب لها. يمكن أيضاً الاستعلام عن مجالٍ ما أي البحث عن عدد العناصر الموجودة بين قيمتين في المصفوفة باستخدام الاستعلامات سابقة الذكر.
يمكن أيضاً تنفيذ استعلامات عن المرتبة بواسطة الإجراء الخاص بالعثور على العنصر الموجود في أقصى اليسار، حيث يُرجع عدد العناصر التي تكون قيمتها أقل من القيمة المستهدفة. ويمكن تنفيذ استعلامات عن المرتبة السابقة باستخدام الاستعلامات عن المرتبة، فإذا كانت مرتبة القيمة المستهدفة هو ، فإن مرتبة القيمة السابقة هي . أما فيما يخص استعلامات مرتبة القيمة اللاحقة، فبالإمكان استخدام الإجراء المُخصص للعثور على العنصر الموجود في أقصى اليمين لأجل ذلك، فإذا كانت نتيجة مرتبة القيمة المستهدفة هي ، فإن مرتبة القيمة اللاحقة لها هي . يُحدد الجار الأقرب للقيمة المستهدفة بالنظر إلى المرتبتين السابقة واللاحقة لها، واختيار أقرب منهما. تٌنفَّذ الاستعلامات عن النطاق حسبَ ما يأتي: قي البداية تُحدد مرتبتي القيمتين، ثُمَّ يُحسَب عدد العناصر ذات القمية المساوية أو الأكبر من الأولى والأقل من القيمة الثانية بإيجاد الفرق بين المرتبتين. يمكن تعديل هذا العدد نحو القيمة الصحيحة التالية أوالسابقة، أي التي تنقص أو تزيد بمقدار واحد، حسبَ طريقة تحديد بداية ونهاية النطاق، أي هل نقطة البداية ونقطة النهاية جزءٌ من النطاق أم لا، وهل تحتوي المصفوفة على عناصر تتطابق قيمتها مع نقاط النهاية أم لا.
