التقسيم الثنائي
تعريف
طريقة البحث الثنائي هي خوارزمية يكون مدخلها عبارة عن قائمة مرتبة من العناصر.
إذا كان العنصر الذي يتم البحث عنه موجودًا في القائمة، فإن البحث الثنائي يعيد موقعه؛ وإلا فإنه يعود فارغًا.
الفكرة الأساسية
- تعتبر هذه الطريقة مناسبة عندما تكون كمية البيانات كبيرة.
- عند استخدام البحث الثنائي، يجب فرز البيانات
- بافتراض أن البيانات تم فرزها بترتيب تصاعدي، بالنسبة لمفتاح قيمة معين، ابدأ المقارنة من الموضع الأوسط في منتصف التسلسل:
- إذا كانت قيمة arr[mid] في الموضع الحالي تساوي key، فإن البحث يكون ناجحًا؛
- إذا كان المفتاح أقل من قيمة الموضع الحالي arr[mid]، فابحث عن arr[low,mid-1] في النصف الأول من التسلسل؛
- إذا كان المفتاح أكبر من قيمة الموضع الحالي arr[mid]، استمر في البحث عن arr[mid+1,high] في النصف الثاني من التسلسل حتى يتم العثور عليه.
تعقيد الوقت:
