البحث الثنائي Binary Search

البحث الثنائي Binary Search

ماهو البحث الثنائي (Binary Search)..؟! وما آلية عمل خوارزمية البحث الثنائي (Binary Search)...؟!! كيف يتم تطبيق البحث الثنائي في أشهر لغات البرمجة…وما أبرز المجالات العملية التي تستفيد منها….؟!!

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

في هذا المقال:

• مقدمة في خورازميات البحث.
• البحث الثنائي Binary Search.
• خطوات خوارزمية البحث الثنائي (Binary Search).
•  خوارزمية البحث الثنائي (Binary Search).
• البحث ثنائي (Binary Search) في لغات البرمجة.
• تطبيقات البحث الثنائي (Binary Search).
• البحث الثنائي (Binary Search) وشجرة البحث الثنائية ( BST).

مقدمة في خورازميات البحث

تتعامل البرمجة مع مشكلة البحث للعثور على قيمة معينة بتطبيق خوارزمية من عدة خوارزميات تسمى خوارزميات البحث منها على سبيل المثال ث المتسلسل المباشر (sequential search) أو ما يعرف بالبحث الخطي (LInear Search) و خوارزمية البحث الثنائي (binary search) الفعالة بشكل مذهل ولكنها محدودة ، والخوارزميات القائمة على تمثيل المجموعة الأساسية في شكل مختلف أكثر ملاءمة للبحث. 

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

وقد تتم عملية البحث في مجموعة محددة (أو مجموعة متعددة تسمح لعدة عناصر بأن يكون لها نفس القيمة). وتسمى القيمة المراد البحث عنها بمفتاح البحث (Search key) ، وعلى عكس خوارزميات الفرز والترتيب (Sort Algorithms )، لا توجد مشكلة في الاستقرار، ولكن تظهر مشكلات مختلفة. على وجه التحديد، في التطبيقات التي قد تتغير فيها البيانات الأساسية بشكل متكرر بالنسبة لعدد عمليات البحث، يجب النظر في البحث جنبًا إلى جنب مع عمليتين أخريين هما الاضافة والحذف.

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

البحث الثنائي (Binary Search)

يمثل البحث الثنائي Binary Search أهم وأشهرالأمثلة على خوارزميات التخفيض بعامل ثابت حيث تعمل هذه الخوارزميات بالتناقص بمقدار عامل ثابت في زمن لوغاريتمي، أي تقليل العمليات مثلاً في في علمية البحث تقليل عدد المقارنات بفعالية.

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

يعمل البحث الثنائي Binary Search على بحث في البيانات مرتبة فهي تقوم بتقسيم البيانات المرتبة إلى قسمين بشكل متكررللعثورعلى قيمة مستهدفة أو إجابة مثالية في وقت لوغاريتمي مقدارة O(log N).

على سبيل المثال في مصفومفة مرتبة تقوم خوارزمية البحث الثنائي Binary Search بمقارنة مفتاح البحث K (القيمة المراد البحث عنها) مع العنصر الأوسط للمصفوفة A[m] . فإذا تطابقت تتوقف الخوارزمية. وبخلاف ذلك، يتم تكرار نفس العملية بشكل متكرر للنصف الأول من المصفوفة ifK <A[m]، أوللنصف الثاني ifK >A[m]:

خطوات خوارزمية البحث الثنائي (Binary Search)

بدلاً من فحص جميع العناصر واحدًا واحدًا (كما في البحث الخطي)، يقوم البحث الثنائي (Binary Search) بالمقارنة مع العنصر الأوسط للقائمة ولتتضح معنا طريقة عمل خوارزمية البحث الثنائي نقدم فيما يلي خطوات Binary Search خطوة بخطوة:

• تحديد نطاق البحث : في بداية البحث لابد أن تحدد الخوارزمية الحدين الأدنى (low) والأعلى (high أو upper) للبحث. في العادة تأخذ الحدود قيم الـ index الاول عنصر واخر عنصر (العناصر مرتبة).
• بداية حلقة البحث: نبدأ حلقة البحث وتسمر طالما أن الحد الأدنى أقل من أو يساوي الحد الأعلى.
• نحدد نقطة المنتصف (mid): إيجاد نقطة المنتصف للمصفوفة نقوم بجمع الحدين الأدنى والأعلى معًا وقسمتهما على 2.
• مقارنة العنصرفي نقطة المنتصف مع العنصر المطلوب وهنا يمكن أن تحدث حالة من الحالات الثلاث التالية:
• حدوث الحالة الأفضل (Best Case) :إذا كان العنصر المطلوب يساوي العنصر الأوسط  فقد تم العثور على القيمة ويتوقف البحث عند عدد مقارنات = 1 (المزيد في مقال عن Big-O).
• أن تكون القيمة المطلوبة أقل من العنصر الأوسط : في هذه الحالة نكرر البحث في النصف الأيسر من القائمة.حيث يُحسب حد أعلى جديد بطرح 1 من القيمة الوسطى بالتالي نقطة المنتصف جديدة.
• أن تكون كانت القيمة المطلوبة أكبر من العنصر الأوسط :  في هذه الحالة نكرر البحث في النصف الأيمن.حيث يُحسب حد أدنى جديد بإضافة 1 إلى القيمة الوسطى وبالتبعية نقطة المنتصف جديدة.
• انتهاء حلقة البحث : نكرر الخطوات حتى نجد العنصر أو تنتهي العناصر دون العثور على العنصر المطلوب  في هذه الحالة تُعاد القيمة -1، أي عدم وجود أي عنصر في المصفوفة مطابق للقيمة المطلوبة.

باختصار، نُهيئ حدود البحث (left وright)، نحسب الموضع الأوسط، ثم نقارن الهدف بالقيمة الوسطى لتضييق النطاق يمينًا أو يسارًا ونكرر حتى نجد العنصر أو ينتهي المجال. هذه الآلية البسيطة تقلّص مساحة البحث بصورة أُسية لتحقق O(log n)—شرط أن تكون البيانات مرتّبة.

 خوارزمية البحث الثنائي (Binary Search)

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

 المخطط الانسيابي لخوارزمية البحث الثنائي Binary Search :

كتابة خوارزمية البحث الثنائي Binary Search بواسطة شبه كود (Pseudocode) :

Binary search
// input --> a sorted array A , target value K
/* return "successful" if the target value is in the array
  or "unsuccessful" if the target value is not in the array */

//The algorithm:
//Declaring and initializing the upper (right) and lower (left) bounds of the array
 -set the upper = array.length - 1
 -set the lower = 0
//if the lower is less or equal upper do the instructions else return "unsuccessful"
while (lower <= upper)
{
  //Declaraiing an integer variable for the midpoint (it must be integer)
  mid = (upper +lower) /2
  //Check the target value if equal the value in the mid 
  if (A[mid] == K)
    return "successful"
  else {
  //Check if the target value is less than mid value. And base on the result, do the suitable changing for upper or lower
     if ( K < A[mid])
       upper  = mid -1
     else 
       lower  = mid +1
     }
}
 return ""unsuccessful"

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

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

البحث الثنائي Binary Search في لغات البرمجة

بعد أن تعرفنا على فكرة خوارزمية البحث الثنائي (Binary Search) وخطوات عملها، من المهم أن نرى كيف يمكن تطبيقها عمليًا في لغات البرمجة المختلفة. فالخوارزمية نفسها تحتفظ بنفس المبدأ في جميع اللغات، إلا أن طريقة كتابتها قد تختلف قليلًا بحسب صياغة اللغة وأسلوبها. سنعرض فيما يلي تمثيلًا عمليًا لخوارزمية البحث الثنائي باستخدام بعض اللغات الشائعة مثل C#، Python، وJavaScript، وذلك لتوضيح كيفية ترجمة الفكرة النظرية إلى كود برمجي قابل للتنفيذ.

خوارزمية البحث الثنائي Binary Search في لغة سي شارب:

...........
public static string BinarySearch (int[] arr, int K) {
	int lower = 0;
    int upper = arr.Length - 1;
    int mid;
    string result;
    while (lower <= upper) {
      //The midpoint must be an integer variable 
       mid = (lower + upper) / 2;
      //Check the target value if equal the value in the mid 
      if (arr[mid] == K) {
        result = "successful";
        return result;
        }
        else {
          //Check  if the target value is less than mid value. And base on the result, do the suitable changing for upper or lower
          if ( K < arr[mid])
            upper  = mid -1;
          else 
            lower  = mid +1;
          }
      }// end loop
      result ="unsuccessful";
      return result; 
		}
...........

خوارزمية البحث الثنائي Binary Search في لغة بايثون :

...........
def BinarySearch(arr, K):
  #Declaring and initializing the upper (right) and lower (left) bounds of the list
  lower = 0
  upper = len(arr) - 1
  while lower <= upper:
    #Declaraiing an intger variable for the midpoint (it must be intger)
    mid = int ((lower + upper) / 2)
    #//Check the target value if equal the value in the mid 
    if arr[mid] == K:
      return "successful"
    #Check if the target value is less than mid value. And base on the result, do the suitable changing for upper or lower
    elif arr[mid] > K:
      upper  = mid - 1
    else:
      lower  = mid + 1
  
  return "unsuccessful"
...........

خوارزمية البحث الثنائي Binary Search في لغة جافا سكريبت :

...........
function BinarySearch(arr, K) {
    //Declaring and initializing the upper (right) and lower (left) bounds of the array
    let lower = 0;
    let upper = arr.length - 1;
    let mid;
    while (upper >= lower) {
	//The midpoint  must be an intger variable 
        mid = Math.floor((upper + lower) / 2);
        if (arr[mid] == K){
          return "successful";
        }
	//Check if the target value is less than mid value. And base on the result, do the suitable changing for upper or lower
        else if (arr[mid] > K)
            upper = mid - 1;
        else
            lower = mid + 1;
    }
    return "unsuccessful";
}
...........

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

يتضح أن خوارزمية البحث الثنائي (Binary Search) تحافظ على نفس المبدأ الأساسي مهما اختلفت لغة البرمجة، حيث تُترجم خطواتها البسيطة والفعّالة إلى شيفرات متنوعة تسهّل استخدامها في التطبيقات العملية.

تطبيقات البحث الثنائي (Binary Search)

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

• البحث في قواعد البيانات: عند البحث عن سجل (مثل اسم، رقم، أو عنوان) في جدول أو فهرس مرتب، تُستخدم خوارزمية البحث الثنائي للوصول إلى النتيجة بسرعة. مثل البحث عن منتج في قائمة أسعار مرتبة أبجديًا.
• البحث في القواميس أو القوائم المترتبة: تستخدم خوارزمية البحث الثنائي في تطبيقات القواميس الإلكترونية تستخدمه لإيجاد الكلمة ومعناها بسرعة. مثل عند كتابة كلمة في قاموس أو مترجم، يتم البحث عنها في قاعدة بيانات مرتبة أبجديًا.
• خوارزميات البحث في الملفات الكبيرة : في أنظمة الملفات (File Systems)، تستخدم أنظمة التشغيل خوارزمية البحث الثنائي للبحث عن ملفات أو فهارس مخزنة بشكل مرتب.
•  تحديد القيم المثلى في المسائل الرياضية: خوارزمية البحث الثنائي لا تقتصر على إيجاد عنصر معين، بل يمكن استخدامها لإيجاد أصغر أو أكبر قيمة تحقق شرطًا معينًا. على سبيل المثال يمكن إيجاد الجذر التربيعي لعدد بدقة عالية، أو أقصى طول قطعة خشب يمكن قصها لعدد معين من الأشخاص.
• ألعاب الفيديو : تستخدم خوارزمية البحث الثنائي في الألعاب لإيجاد الإحداثيات أو كائنات اللعبة في خرائط مرتبة.
• محركات البحث: تستخدم خوارزمية البحث الثنائي في محركات البحث للعثور بسرعة على الكلمة المفتاحية في فهارس البحث.
• تحديد نقطة التغيير (Change Point) : إذا كان لدينا بيانات تحتوي على انتقال من حالة إلى أخرى (مثل قائمة من الأصفار ثم الآحاد)، يمكن استخدام خوارزمية البحث الثنائي لإيجاد نقطة التغيير بسرعة.

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

البحث الثنائي (Binary Search) وشجرة البحث الثنائية (Binary Search Tree - BST)

يمكن اعتبار الشجرة الثنائية للبحث (Binary Search Tree - BST) وكأنها تطبيق "مرن" على البحث الثنائي Binary Search:

• حيث تعتمد خوارزمية البحث الثنائي Binary Search على مصفوفة و نبدأ البحث من العنصر الأوسط.
• بينما تعتمد الشجرة الثنائية للبحث (Binary Search Tree - BST) العقدة الجذرية (Root) كعنصر أوسط فنقسم البيانات إلى شجرة يسار (أصغر) وشجرة يمين (أكبر).
• عملية البحث في شجرة البحث الثنائية BST تشبه تمامًا خطوات البحث الثنائي لكن باستخدام المؤشرات بدل الفهرسة (indexing).

مما سبق نرى تشابه الشجرة الثنائية للبحث (Binary Search Tree - BST) مع خوارزمية البحث الثنائي (Binary Search) في أمور منها اعتماد مبدأ التقسيم إلى نصفين في البحث والعمل مع بيانات مرتبة ، لكن لكل منهما طريقة عمل أي ثمة فروق بينهما فيما نوضح أوجه الشبه والاختلاف بينهما:

1. أوجه التشابه

• الفكرة الأساسية: كلاهما يقلل عدد العناصر التي يتم فحصها عن طريق تقسيم المساحة أو البيانات إلى قسمين في كل خطوة.
• الترتيب مهم: في خوارزمية البحث الثنائي تحتاج بيانات مرتبة، والشجرة الثنائية للبحث (Binary Search Tree - BST) تحفظ بياناتها بترتيب معيّن ليسهّل البحث.
• خطوات البحث متشابهة: في خوارزمية البحث الثنائي (Binary Search)على مصفوفة، نذهب للنصف الأيمن أو الأيسر حسب المقارنة. في الشجرة الثنائية للبحث (BST)، نذهب لابن اليمين أو ابن اليسار حسب المقارنة.

2. الاختلافات

يمكن تلخيص الاختلاف فيما يلي:

التخزينتخزين متتابع في الذاكرة مثلاً (List أو Array)تخزين غير متتابع باستخدام مؤشرات/ روابط

وجة الاختلاف	البحث الثنائي (Binary Search)	الشجرة الثنائية (Binary Tree / BST)
نوع البنية	قائمة/مصفوفة مرتبة	هيكل بيانات شجري يحتوي على عقد وروابط
الترتيب	البيانات مرتبة مسبقًا	الترتيب يتحقق تلقائيًا عند إدخال العناصر
التعقيد	O(log n) في البحث	O(log n) في البحث (إذا كانت الشجرة متوازنة)
الإضافة والحذف	صعبة نسبيًا في المصفوفات	أسهل في الشجر، لا تحتاج إعادة ترتيب كبيرة

الخلاصة أن البحث الثنائي Binary Search هو خوارزمية، بينما الشجرة الثنائية هي هيكل بيانات، والشجرة الثنائية للبحث هي دمج للفكرتين بحيث تطبق مبدأ البحث الثنائي على هيكل شجري بدل المصفوفة. و للمزيد حول هياكل البينات الشجرية يمكن الاطلاع على مقالات هياكل البيانات الشجرية Trees والأشجار الثنائية Binary Trees.

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