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

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

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

1. كغيرها من الخوارزميات لا بد من توافر المدخلات المطلوبة. و التي تتمثل في العُنصر المراد البحث عنه و المصفوفة التي سيتم البحث فيها.
2. يجب أن تكون المصفوفة مرتباً تصاعدياً (من الأصغر إلى الأكبر). في حال لم تكن المصفوفة مرتبة تصاعدياً يجب عليك أن ترتبها تصاعدياً حتى تستطيع تطبيق خوارزمية البحث الثنائي.
3. مصفوفة البحث لها فهرس (Index) يبدأ من الصفر أو الواحد، لكليهما نفس النتيجة.
4. تبدأ الخوارزمية عملها بوضع مؤشر الفهرس في وسط المصفوفة حتى تقسم المصفوفة إلى قسمين. و هنا بداية الإستفادة الفعلية من مبدأ (فرّق تسُد).
5. إذا خطر على بالك هذا التساؤل “توجد مصفوفات عدد عناصرها زوجي و أخرى عدد عناصرها فردي فكيف يكون مؤشر المصفوفة في الحالتين في الوسط؟؟ ” فأهنئُك على هذا التفكير. إن عملية إختيار وسط المصفوفة بسيطة و سهلة، كل ما عليك إتباع المعادلة التالية:
   و تعني هذه المعادلة (floor( (low  + high) /2  فيكون وسط مصفوفة عناصرها 5 هو العنصر الثاني، و وسط مصفوفة عناصرها 4 أيضاً العنصر الثاني.
   
6. تتم مقارنة العنصر بالوسط (حيثُ المؤشر) بالعُنصر المُراد البحث عنه و النتيجة إحدى ثلاث حالات:
   1. أن تساوي قيمة العُنصر بالمصفوفة قيمة العُنصر المراد البحث عنه. و بالتالي يتم الإحتفاظ بقيمة مؤشر الفهرس و يوقف البحث.
      
   2. أو تكون قيمة العنصر المراد البحث عنه أكبر من قيمة العنصر حيث المؤشر. في هذه الحالة يتم تجاهل جميع عناصر النصف الأيسر من المصفوفة و يصبح الجزء الأيمن من المصفوفة مدخلاً جديداً لعملية بحث عن طريق خوارزمية البحث الثنائي.
      
   3. أن تكون قيمة العُنصر المراد البحث عنه أقل من قيمة العنصر حيثُ المؤشر. في هذه الحالة يتم تجاهل جميع عناصر النصف الأيمن من المصفوفة و يصبح الجزء الأيسر من المصفوفة مدخلاً جديداً لعملية بحث عن طريق خوارزمية البحث الثنائي.
      
7. تُكرر عملية البحث (الخطوة 6) في النصف المتُبقي حتى يتم الوصول إلى خانة واحدة فقط تمثل موقع العنصر المُراد البحث عنه.

مهمة الدالة floor هي إيجاد أكبر قيمة صحيحة ( ليست كسر) أقل من القيمة المُستقبلة في الدالة. أمثلة : floor(3.9) = 3 ، floor(100.1) = 100 ،  floor(-10.3) = -11

حساب أفضل و أسواء حالة لخوارزمية البحث الثنائي

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

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

عندما تكون المصفوفة ذات عدد عناصر فردي (لنفرض 9)، و نختار العُنصر الأوسط حيث نضع مؤشر الفهرس (العنصر رقم 5) تتبقى 4 عناصر من اليمين و كذلك 4 عناصر من اليسار، ما يعني أن العُنصر إذا كان أكبر أو أصغر من العُنصر الأوسط فإن عدد العناصر التي تم تجاهلها سيكون 5 ( 4 عناصر بأحد الإتجاهين بالإضافة إلى العُنصر الوسطي).
تظهر المُشكلة عندما يكون عدد عناصر المصفوفة زوجي، فإذا كان عدد عناصر المصفوفة 8، فوفقاً لمعادلة إختيار وسط المصفوفة المذكورة أعلاه يكون وسط المصفوفة هو العنصر رقم 4، بالتلي تتبقى 4 عناصر من الإتجاه الأيمن و 3 في الإتجاه الأيسر، أليس كذلك؟!!

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

• عدد عناصر المصفوفة إما فردي أو زوجي.
• عندما يكون عدد عناصر المصفوفة فردي فإن عدد العناصر المتبقية يتساوى.
• عندما يكون عدد عناصر المصفوفة زوجي فإن عدد العناصر المتبقية في الجانب الأيمن أكبر من الأيسر.

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

الكود التقريبي لخوارزمية البحث الثنائي Binary Search Pseudo Code

Input: An array A[1..n] of n elements sorted in nondecreasing order and an
element x.
Output: j if x = A[j]; 1 <= j <= n; and 0 otherwise.
 low=1; high=n; j=0
 while (low <= high) and (j = 0)
 mid=floor( (low + high)/2 )
 if x = A[mid] then j=mid
 else if x < A[mid] then high=mid - 1
 else low=mid + 1
 end while
 return j

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

int[] data;
    int size;

    public boolean binarySearch(int key) 
    {
         int low = 0;
         int high = size - 1;
          
         while(high >= low) {
             int middle = (low + high) / 2;
             if(data[middle] == key) {
                 return true;
             }
             if(data[middle] < key) {
                 low = middle + 1;
             }
             if(data[middle] > key) {
                 high = middle - 1;
             }
        }
        return false;
   }

شُكراً على تواجدك في مدونة علوم و أتمنى لك أن تكون قد إستفدت من هذه التدوينة

مقالات مفيدة لك:

 خوارزمية الترتيب بالإختيار: الشرح السهل مع التنفيذ

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