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

سيتعلم هذا البرنامج التعليمي كيف يمكننا تطبيق خوارزمية بحث ثنائية باستخدام Python للعثور على موضع فهرس العنصر في القائمة المحددة.

مقدمة

البحث الثنائي هو خوارزمية للعثور على عنصر معين في القائمة. لنفترض أن لدينا قائمة بآلاف العناصر، ونحتاج إلى الحصول على موضع فهرس لعنصر معين. يمكننا العثور على موضع فهرس العنصر بسرعة كبيرة باستخدام خوارزمية البحث الثنائي.

هناك العديد من خوارزميات البحث ولكن البحث الثنائي هو الأكثر شيوعًا فيما بينها.

يجب فرز العناصر الموجودة في القائمة لتطبيق خوارزمية البحث الثنائي. إذا لم يتم فرز العناصر، فقم بفرزها أولاً.

دعونا نفهم مفهوم البحث الثنائي.

مفهوم البحث الثنائي

في خوارزمية البحث الثنائي، يمكننا العثور على موضع العنصر باستخدام الطرق التالية.

كات تيمبف أخت

طريقة العودية
الطريقة التكرارية

أسلوب فرق تسد يتبعه الأسلوب العودي. في هذه الطريقة، يتم استدعاء الدالة نفسها مرارًا وتكرارًا حتى يتم العثور على عنصر في القائمة.

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

يعد البحث الثنائي أكثر فعالية من البحث الخطي لأننا لا نحتاج إلى البحث في فهرس كل قائمة. يجب فرز القائمة لتحقيق خوارزمية البحث الثنائي.

دعونا ننفذ خطوة بخطوة البحث الثنائي.

لدينا قائمة مرتبة من العناصر، ونبحث عن موضع الفهرس 45.

[12، 24، 32، 39، 45، 50، 54]

لذلك، قمنا بوضع مؤشرين في قائمتنا. يتم استخدام مؤشر واحد للدلالة على القيمة الأصغر التي تسمى قليل ويستخدم المؤشر الثاني للدلالة على أعلى قيمة تسمى عالي .

بعد ذلك نحسب قيمة وسط عنصر في المصفوفة.

 mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer)

الآن، سنقوم بمقارنة العنصر الذي تم البحث عنه بقيمة الفهرس الأوسط. في هذه الحالة، 32 لا يساوي أربعة خمسة. لذا علينا إجراء المزيد من المقارنة للعثور على العنصر.

إذا كان الرقم الذي نبحث عنه يساوي المنتصف. ثم العودة منتصف وإلا انتقل إلى مزيد من المقارنة.

الرقم المراد البحث عنه أكبر من وسط الرقم، نقوم بمقارنة ن مع العنصر الأوسط من العناصر الموجودة على الجانب الأيمن من منتصف وتعيين منخفض ل منخفض = متوسط + 1.

وإلا قارن ن مع ال العنصر الأوسط من العناصر الموجودة على الجانب الأيسر من منتصف وحدد عالي ل عالية = منتصف - 1.

كرر ذلك حتى يتم العثور على الرقم الذي نبحث عنه.

تنفيذ بحث ثنائي في بايثون

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

دعونا نفهم البرنامج التالي للطريقة التكرارية.

تنفيذ بايثون

 # Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let&apos;s understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let&apos;s understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;) </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can&apos;t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=>

توضيح:

في البرنامج أعلاه -

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

دعونا نفهم الطريقة العودية للبحث الثنائي.

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

يمكن استخدام طريقة العودية في البحث الثنائي. في هذا، سوف نقوم بتعريف دالة عودية تستمر في استدعاء نفسها حتى تستوفي الشرط.

com.mylivecricket.

دعونا نفهم البرنامج أعلاه باستخدام الدالة العودية.

برنامج بايثون

 # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;)

انتاج:

 Element is present at index 2

توضيح

البرنامج أعلاه مشابه للبرنامج السابق . لقد أعلنا عن وظيفة العودية وحالتها الأساسية. الشرط هو أن أدنى قيمة أصغر أو تساوي أعلى قيمة.

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

في الجزء الأخير، كتبنا برنامجنا الرئيسي. إنه نفس البرنامج السابق، لكن الاختلاف الوحيد هو أننا قمنا بتمرير معلمتين في ملف بحث ثنائي() وظيفة.

وذلك لأننا لا نستطيع تعيين القيم الأولية للقيم المنخفضة والعالية والمتوسطة في الدالة العودية. في كل مرة يتم استدعاء العودية سيتم إعادة تعيين القيمة لتلك المتغيرات. وهذا سوف يعطي نتيجة خاطئة.

تعقيد

تعقيد خوارزمية البحث الثنائي هو يا(1) لأفضل حالة. يحدث هذا إذا تم العثور على العنصر الذي نبحث عنه في المقارنة الأولى. ال يا (تسجيل الدخول) هو أسوأ ومتوسط تعقيد حالة البحث الثنائي. يعتمد هذا على عدد عمليات البحث التي يتم إجراؤها للعثور على العنصر الذي نبحث عنه.

خاتمة

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

لقد ناقشنا كلتا الطريقتين للعثور على موضع الفهرس للرقم المحدد.