تنفيذ خوارزميات البحث الثنائي Binary Search في القواميس والقوائم في Python

تستخدم خوارزميات البحث الثنائي (Binary Search) للبحث في البيانات المرتبة، وتُنفذ تلك الخوارزميات بشكل أكثر شيوعًا في القوائم المرتبة (lists)، لكن باستطاعتك تنفيذها في القواميس (dictionaries) في لغة Python.

فعند استخدام البحث الثنائي في القواميس، يتم البحث عن القيمة المطلوبة باستخدام المفتاح (key) بدلاً من الموضع (index) كما هو الحال في القوائم، ويجب أن يكون للقاموس ترتيب معين للمفاتيح لضمان عمل البحث الثنائي بشكل صحيح.

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

وإليك مثال لتوضيح تنفيذ خوارزمية البحث الثنائي في قاموس (dictionary):

def binary_search_dict(dictionary, target):
    keys = sorted(dictionary.keys())  # ترتيب المفاتيح بشكل صحيح
    left = 0
    right = len(keys) - 1

    while left <= right:
        mid = (left + right) // 2
        mid_key = keys[mid]

        if mid_key == target:
            return dictionary[mid_key]
        elif mid_key < target:
            left = mid + 1
        else:
            right = mid - 1

    return None  # في حالة عدم العثور على القيمة المطلوبة

# مثال لاستخدام البحث الثنائي في قاموس
my_dict = {'apple': 5, 'banana': 2, 'cherry': 8, 'orange': 3, 'pear': 1}

result = binary_search_dict(my_dict, 'cherry')
if result is not None:
    print("تم العثور على القيمة:", result)
else:
    print("لم يتم العثور على القيمة")

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

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

وفيما يلي  مثال على تنفيذ خوارزمية البحث الثنائي للبحث عن رقم في قائمة (list):

def binary_search_list(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        mid_num = nums[mid]

        if mid_num == target:
            return mid
        elif mid_num < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # في حالة عدم العثور على الرقم

# مثال لاستخدام البحث الثنائي في قائمة
my_list = [1, 3, 5, 7, 9, 11, 13, 15]

index = binary_search_list(my_list, 7)
if index != -1:
    print("تم العثور على الرقم في الموضع:", index)
else:
    print("لم يتم العثور على الرقم")

ولتوضيح الأمر سأذكر لك مثال للبحث عن  اسم في قائمة (list):

def binary_search_names(names, target):
    left = 0
    right = len(names) - 1

    while left <= right:
        mid = (left + right) // 2
        mid_name = names[mid]

        if mid_name == target:
            return mid
        elif mid_name < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # في حالة عدم العثور على الاسم

# مثال لاستخدام البحث الثنائي في قائمة الأسماء
name_list = ['Alice', 'Bob', 'Charlie', 'David', 'Eve', 'Frank', 'Grace']

index = binary_search_names(name_list, 'David')
if index != -1:
    print("تم العثور على الاسم في الموضع:", index)
else:
    print("لم يتم العثور على الاسم")

بتاريخ 8 دقائق مضت قال Mustafa Suleiman:

تستخدم خوارزميات البحث الثنائي (Binary Search) للبحث في البيانات المرتبة، وتُنفذ تلك الخوارزميات بشكل أكثر شيوعًا في القوائم المرتبة (lists)، لكن باستطاعتك تنفيذها في القواميس (dictionaries) في لغة Python.

فعند استخدام البحث الثنائي في القواميس، يتم البحث عن القيمة المطلوبة باستخدام المفتاح (key) بدلاً من الموضع (index) كما هو الحال في القوائم، ويجب أن يكون للقاموس ترتيب معين للمفاتيح لضمان عمل البحث الثنائي بشكل صحيح.

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

وإليك مثال لتوضيح تنفيذ خوارزمية البحث الثنائي في قاموس (dictionary):

def binary_search_dict(dictionary, target):
    keys = sorted(dictionary.keys())  # ترتيب المفاتيح بشكل صحيح
    left = 0
    right = len(keys) - 1

    while left <= right:
        mid = (left + right) // 2
        mid_key = keys[mid]

        if mid_key == target:
            return dictionary[mid_key]
        elif mid_key < target:
            left = mid + 1
        else:
            right = mid - 1

    return None  # في حالة عدم العثور على القيمة المطلوبة

# مثال لاستخدام البحث الثنائي في قاموس
my_dict = {'apple': 5, 'banana': 2, 'cherry': 8, 'orange': 3, 'pear': 1}

result = binary_search_dict(my_dict, 'cherry')
if result is not None:
    print("تم العثور على القيمة:", result)
else:
    print("لم يتم العثور على القيمة")

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

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

وفيما يلي  مثال على تنفيذ خوارزمية البحث الثنائي للبحث عن رقم في قائمة (list):

def binary_search_list(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        mid_num = nums[mid]

        if mid_num == target:
            return mid
        elif mid_num < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # في حالة عدم العثور على الرقم

# مثال لاستخدام البحث الثنائي في قائمة
my_list = [1, 3, 5, 7, 9, 11, 13, 15]

index = binary_search_list(my_list, 7)
if index != -1:
    print("تم العثور على الرقم في الموضع:", index)
else:
    print("لم يتم العثور على الرقم")

ولتوضيح الأمر سأذكر لك مثال للبحث عن  اسم في قائمة (list):

def binary_search_names(names, target):
    left = 0
    right = len(names) - 1

    while left <= right:
        mid = (left + right) // 2
        mid_name = names[mid]

        if mid_name == target:
            return mid
        elif mid_name < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # في حالة عدم العثور على الاسم

# مثال لاستخدام البحث الثنائي في قائمة الأسماء
name_list = ['Alice', 'Bob', 'Charlie', 'David', 'Eve', 'Frank', 'Grace']

index = binary_search_names(name_list, 'David')
if index != -1:
    print("تم العثور على الاسم في الموضع:", index)
else:
    print("لم يتم العثور على الاسم")

 

شكرا جدااا لحضرتك

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

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

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

كذلك الأمر بالنسبة للمجموعات set فالبحث فيها سريع جداً.

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