قمنا بتقسيم مجموعة من العناصر إلى نصفين في البحث الثنائي لتقليل عدد المقارنات المباشرة اللازمة لاكتشاف عنصر ما. ومع ذلك، هناك متطلب واحد: يجب فرز عناصر المصفوفة مسبقًا.
بحث ثنائي
ال بحث ثنائي تحدد الطريقة موقع فهرس عضو قائمة معين. وهي من بين الخوارزميات الأكثر شعبية والأسرع. لكي يتم تشغيل إجراء البحث الثنائي، يجب فرز الإدخالات الموجودة في القائمة.
لا
بحث ثنائي هي تقنية بحث أكثر كفاءة لتحديد موقع فهرس العنصر من البحث الخطي نظرًا لأنه ليس علينا فحص كل فهرس قائمة.
يمكن تلخيص العملية الكاملة لخوارزمية البحث الثنائي في الخطوات التالية:
- حدد موقع العنصر الأوسط في المصفوفة التي تم فرزها.
- قم بإجراء مقارنة بين العنصر المراد تحديد موقعه والعنصر الأوسط.
- إذا كان هذا العنصر يساوي العنصر الأوسط في القائمة المحددة، فسيتم إرجاع فهرس العنصر الأوسط. وبخلاف ذلك، ستقوم الخوارزمية بمقارنة العنصر بالعنصر الموجود في المنتصف.
- الآن، إذا كان العنصر الذي سيتم تحديد موقعه أكبر من العنصر الأوسط في القائمة، فسيتم مقارنته بالنصف الأيمن من القائمة، أي العناصر بعد الفهرس الأوسط.
- أو إذا كان العنصر أقل من العنصر الموجود في منتصف القائمة، فسيتم مقارنته بالنصف الأيسر فقط من القائمة، أي العناصر التي تسبق الفهرس الأوسط.
البحث الثنائي العودي
يتضمن البحث الثنائي تقسيم الفاصل الزمني للبحث بشكل مستمر إلى جزأين متساويين لاكتشاف عنصر في مصفوفة مرتبة، ويستلزم البحث الثنائي المتكرر تقسيم إجراء البحث الثنائي الكامل إلى مشكلات أصغر. البحث الثنائي العودي هو إجابة العودية للبحث الثنائي.
فيما يلي الخصائص التي يجب أن تلبيها الحلول العودية بالكامل:
- الحالة الأساسية مطلوبة للنهج العودي.
- يجب أن تكون هناك حالة اختبار متكررة في النهج العودي.
- يجب أن يقترب النهج العودي من الحالة الأساسية.
يتم تمثيل أدنى تقسيم فرعي لمشكلة معقدة من خلال الحالة الأساسية، وهي الحالة النهائية. لذلك، لإجراء البحث الثنائي بالطريقة العودية، يجب أن تحتوي الخوارزمية لدينا على حالة أساسية وحالة متكررة، مع تقدم الحالة العودية إلى الحالة الأساسية. وإلا فلن تنتهي العملية أبدًا وستؤدي إلى حلقة لا نهاية لها.
تعمل تقنية البحث الثنائي على تقليل الوقت المستغرق للعثور على عنصر محدد داخل مصفوفة مفروزة. غالبًا ما يتم تنفيذ طريقة البحث الثنائي بشكل متكرر، ولكن يمكننا أيضًا تنفيذها بشكل متكرر عن طريق تقسيمها إلى أجزاء أصغر.
شفرة
1 مليون بالأرقام
#defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!')
انتاج:
The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list
العودية هي تقنية برمجة وحل المشكلات قوية للغاية. قد نستخدمها لتقييم وتنفيذ مجموعة متنوعة من الخوارزميات، بدءًا من المشكلات التكرارية البسيطة إلى مشكلات التراجع المعقدة. في هذا البرنامج التعليمي، نظرنا إلى استخدام لغة بايثون لإنشاء طريقة البحث الثنائي العودية.