خوارزمية البحث الثنائي هي خوارزمية تستخدم في البحث عن قيمة معينة في مصفوفة مرتبة بشكل تصاعدي. وهي تتألف من الخطوات التالية:
1- التحقق من منتصف العناصر في المصفوفة.
2- إذا كانت القيمة المطلوبة أكبر من القيمة في النصف الأيمن من المصفوفة، يتم تكرار الخطوة الأولى فقط مع النصف الأيمن من المصفوفة.
3- إذا كانت القيمة المطلوبة أقل من القيمة في النصف الأيسر من المصفوفة، يتم تكرار الخطوة الأولى فقط مع النصف الأيسر من المصفوفة.
4- في حال وجود القيمة المطلوبة في نصف العناصر، تم العثور على القيمة المطلوبة.
وفيما يلي، نقدم تنفيذ خوارزمية البحث الثنائي باستخدام لغة الجمع الأسمبلي في emu8086:
“`assembly
.model small
.stack 100
.data
arr1 db 5, 7, 9, 11, 13, 15, 17, 19, 21, 23
val db 17
.code
main proc
mov ax, @data
mov ds, ax
mov bl, 0 ; العنصر الأول في المصفوفة
mov bh, 9 ; العنصر الأخير في المصفوفة
mov al, val ; القيمة المراد البحث عنها
search:
mov cl, bl ; تخزين عنوان العنصر الأول في التسلسل
add cl, bh ; العنصر الأخير في المصفوفة
shr cl, 1 ; حساب المنتصف بين العناصر الأول والأخير في المصفوفة
mov dl, arr1[cl] ; حفظ العنصر الحالي في المتغير dl
cmp al, dl ; تحقق مما إذا كان العنصر الحالي هو القيمة المراد البحث عنها
je found
jg greater
jl smaller
greater:
mov bl, cl ; البحث في النصف الأيمن من المصفوفة
inc bl ; تزيد بمقدار 1 للحفاظ على جزء متساوٍ من اليمين
jmp search
smaller:
mov bh, cl ; البحث في النصف الأيسر من المصفوفة
dec bh ; ينقص بمقدار 1 للحفاظ على جزء متساوٍ من اليسار
jmp search
found:
mov ah, 4Ch
int 21h
main endp
end main
“`
في هذا المثال، تم إنشاء مصفوفة arr1 التي تحتوي على العناصر المرتبة بشكل تصاعدي، ثم تم تهيئة المتغير val بالقيمة التي يجب البحث عنها. في العمود الثاني من البرنامج، يتم تعيين بداية المصفوفة إلى متغير الرأس (bl) ونهايتها إلى متغير الذيل (bh). تم تعيين قيمة val إلى المسجل (al).
يبدأ البرنامج المشغل بإنشاء بيئة البرنامج وتهيئة متغيراته، ثم يقوم بتنفيذ حلقة البحث. تم تخزين عنوان العنصر الأول في المتغير bl وعنوان العنصر الأخير في المتغير bh. يتم حساب العنصر الأوسط باستخدام mov cl، Add cl، shr cl وتخزين النتيجة في المتغير cl.
تم التصدي لـ 3 حالات مختلفة (يتم التفرع باستخدام jg، Jl وعلامات الانتقال je). في حالة العثور على العنصر المراد البحث عنه، يتم الانتقال إلى العلامة (found) وتنفيذ إجراءات إضافية (في هذه الحالة، نقوم بإخراج رمز انتهاء البرنامج). أما إذا كان العنصر الحالي أكبر من القيمة المراد البحث عنها، يتم الانتقال إلى العلامة (greater) والبحث في النصف الأيمن من المصفوفة. وعلى النقيض، إذا كان العنصر الحالي أصغر من القيمة المراد البحث عنها، يتم الانتقال إلى العلامة (smaller) والبحث في النصف الأيسر من المصفوفة.
وهذا هو كل شيء! بمجرد الانتهاء من حلقة البحث، يتم الخروج من البرنامج.
