خوارزمية البحث الثنائي في بايثون

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

a=[3,2,3,5,6,4,7]
x=int(input())
a=sorted(a)
start,end=0,len(a)
y=-1
while(start<=end):
      mid=(start+end)//2
      if(a[mid]==x):
            y=mid
            break
      if(x>a[mid]):
           start=mid+1
      else:
           end=mid-1
if(y==-1):
    print("Number not found")
else:
    print("Number found in index {}".format(y))

في البداية إدخال العدد المراد البحث عنه
بعد ذلك ترتيب المصفوفه لأن شرط البحث الثنائي هو ان تكون المصفوفه مرتبه
بعد ذلك تعيين قيمة البداية صفر وقيمة النهاية ب طول المصفوفه
أعطاء y=-1 وذلك يعني أن العدد في البداية لا يعتبر موجود
بعد ذلك حلقه شرط الحلقه يكون دوما البداية أصغر من النهايه
بعد ذلك اسناد قيمة الاندكس الذي في الوسط إلى mid
بعد ذلك عمليات المقارنه التي ذكرناها في حالة التساوي نقوم بإسناد قيمة mid إلى y
في حالة x أكبر من القيمه التي في الوسط هذا يعني أنها أكبر من جميع قيم النصف الأيسر من المصفوفه بالتالي تصبح البداية الجديدة mid+1
في حالة x أصغر من القيمه التي في الوسط هذا يعني أنها أصغر من جميع قيم النصف الأيمن من المصفوفه بالتالي تصبح النهاية الجديدة mid-1
بعد اختلال الشرط نخرج من الحلقه فإذا تغيرت قيمة y هذا يعني أنه موجود ونقوم بطباعة موجود وإذا كان يساوي -1 هذا يعني أنه غير موجود

يمكن تطبيق البحث الثنائي في بايثون كالتالي:

نقوم بعمل دالة search ونمرر لها القائمة ومن أين يبدء البحث وأين ينتهي وكذلك العنصر الذي نبحث عنه

def search (lst, l, r, x): 

	# نتحقق من القيمة الأولية
  # المتغير r يجب أن يكون أكبر من l
	if r >= l: 
    # نستعمل علامة القسمة المزدوجة لجلب القيمة الصحيحة فقط
		mid = l + (r - l)//2

		# نادرًا ما يكون العنصر في وسط القائمة لكن إن وجد نقوم بإرجاعه مباشرة
		if lst[mid] == x: 
			return mid 
		
		# إن كان العنصر المعطى أصغر من العنصر الموجود في وسط القائمة
    # فإنه سيكون موجودًا في الجزء الأيسر من القائمة
		elif lst[mid] > x: 
			return search(lst, l, mid-1, x) 
		else: 
      # العنصر موجود في الجزء الأيمن
			return search(lst, mid + 1, r, x) 

	else: 
		# إن لم يكن العنصر موجود في القائمة من البداية نقوم بإرجاع -1
		return -1

myList = [ 1, 2, 3, 4, 5, 6, 7, 8 ] 
x = 6

result = search(myList, 0, len(myList)-1, x) 

if result != -1: 
	print (f"The Element is at {result}")
else: 
	print ("The List doesn't contain the element")

لاحظي أن القائمة التي نقوم بتمريرها إلى دالة search يجب أن تكون مرتبة تصاعديًا لكي تعمل الدالة بشكل سليم، ويمكن ترتيب أي قائمة من خلال التابع sort كالتالي:

cars = ['Ford', 'BMW', 'Volvo']
cars.sort()
print(cars)	# Output: ['BMW', 'Ford', 'Volvo']

بإختصار البحث الثنائي سريع جداً مقارنة بالبحث الخطي ، لأن البحث الخطي سيمُر على جميع العناصر من البداية الى النهاية

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

لكن إذا كان لديك قائمة طويلة من العناصر فيمكنك مباشرةً إستخدام البحث الخطي

ولكن في البحث الثنائي يجب عليك فرز العناصر بالترتيب اولاً إذا لم تكن العناصر مرتبة من قبل

وهذا الكود يبين كيفية ذلك

a=[3,2,3,5,6,4,7]
# فرز العناصر بالترتيب اولاً
a = sorted(a)

# تعريف دالة البحث الثنائي
def binarySearch(arr, l, r, x):
 
    while l <= r:
 
        mid = l + (r - l) // 2;
         
        # التأكد إذا كان العنصر المراد البحث عنه موجود في الوسط
        if arr[mid] == x:
            return mid
 
        # التأكد إذا كان العنصر المراد البحث عنه أكبر ، ويتم تجاهل النصف الأيسر
        elif arr[mid] < x:
            l = mid + 1
 
        # التأكد إذا كان العنصر المراد البحث عنه أكبر ، ويتم تجاهل النصف الأيمن
        else:
            r = mid - 1
     
    # إذا وصلنا الى هنا فهذا يعني ان العنصر غير موجود
    return -1
 
# العدد الذي تبحث عنه
x = 4
 
# إستدعاء دالة البحث
result = binarySearch(arr, 0, len(arr)-1, x)
 
if result != -1:
    print ("العنصر موجود في الفهرس رقم % d" % result)
else:
    print ("العنصر غير موجود في القائمة")