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

15  تعليق

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

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

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

  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;
   }

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

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

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

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

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

طريقة عمل خوارزمية الترتيب الفقاعي

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

  1. الفكرة الاساسية لخوارزمية الترتيب الفقاعي هي أن تضع أكبر عنصر في المصفوفة في مكانه الصحيح في كل دورة.
  2. ماذا يحدث في كل دورة؟ تضع المؤشر في أول عنصر بالمصفوفة، ثم تقارنه مع العُنصر التالي:
    1. إذا كان العنصر الأول أصغر من العنصر الثاني، أنقل المؤشر إلى العنصر التالي (لا يوجد تبديل).
    2. إذا كان العنصر الأول أكبر من العنصر الثاني، بدل العنصر الثاني مع العنصر الأول ثم أنقل المؤشر إلى العنصر التالي (يوجد تبديل).
    3. نواصل العملية حتى العنصر قبل الأخير بالمصفوفة.
  3. عدد عناصر المصفوفة التي ترتبها خوارزمية الترتيب الفقاعي في كل دورة تقل بواحد حتى تنتهي العناصر، فإذا كان عدد عناصر المصفوفة 5، ففي الدورة الثانية ستُرتب 4 و الدورة الثالثة ستُرتب 3 عناصر و هكذا. لماذا؟ لأنه في كل دورة تضع الخوارزمية عنصراً في مكانه الصحيح، فبالتالي لا نحتاج لإدخاله في عملية الترتيب مرة أخرى.
  4. عدد الدورات = عدد عناصر المصفوفة – 1، لماذا؟ حاول تخيلها… حسناً، في أول دورةنأخذ العناصر كاملة، و يقل عدد العناصر بواحد كلما إنتقلنا إلى دورة التالية و هكذا حتى نصل إلى أن يكون عدد العناصر المتبقية 2. هنا.. إذا كانت العناصر مرتبة فقد إكتمل الترتيب، و إذا لم تكن مرتبة فسترتبها و إكتمل الترتيب، أليس كذلك؟ إذاً فما فائدة ترتيب العنصر الأخير لوحده؟ لهذا تجد أن عدد الدورات في خوارزمية الترتيب الفقاعي = عدد العناصر – 1.
  5. إذا ما كانت المصفوفة مرتبة أصلاً، و أجريت عليها خوارزمية الترتيب الفقاعي، كيف تعرف أن المصفوفة مرتبة مسبقاً؟ فكّر و تفكّر.. إذا ما وجدت أن الخوارزمية أكلمت دورة كاملة دون أن تجري عملية تغيير واحدة، عندها تعلم أن المصفوفة مرتبة (هذه قاعدة إنتبه لها).
  6. في أي مرحلة إذا ما علمت أن مصفوفتك مرتبة فلا داعي لإكمال خوارزمية الترتيب الفقاعي، و ذلك بإستخدام القاعدة السابقة، فقد يكون العنصر الأول و الثاني فقط في غير موضعهم، و بإجراء أول عملية تبديل يكون قد إكتمل ترتيب المصفوفة. في الدورة التالية لن يحدث أي تبديل و بذلك تكون قد علمت أن المصفوفة مرتبة… أوقف الخوارزمية. كيف توقفها؟ هكذا تسأل؟ سترى بشفرة الجافا أدناه.

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

خوارزمية الترتيب الفقاعي

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

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

الدورة الأولى من خوارزمية الترتيب الفقاعي

  • وُضع المؤشر بالعنصر رقم 1، تمت مقارنته بالعنصر رقم 2. 5<12 إذا لا يوجد تغيير، نضع المؤشر على العنصر الثاني.
  • 12>9، إذا في هذه الحالة وفقاً لمفاهيم الخوارزمية ماذا نفعل؟ نجري عملية تبديل، فيأخذ 12 مكان 9 و 9 تأخذ مكان 12، ننقل المؤشر إلى العنصر التالي. ركز جداً سيكون العنصر التالي هو الرقم 12. لماذا؟ لأن المؤشر إنتقل من العنصر رقم 2 إلى العنصر رقم 3، عملية التبديل ليس لها أي تأثير على مكان المؤشر فالمؤشر أعمى أبكم أصم. عندما يأتي دوره ينفذ ما عليه بالإنتقال إلى العنصر التالي دون أن يراعي ماذا جرى قبل أو بعد.
  • 12>7، إذا نجري نفس العملية السابقة، تبديل بين 12 و 7، و ينتقل المؤشر إلى العنصر الرابع و هو 12.
    لأن العنصر رقم 12 هو أكبر عنصر بالمصفوفة فسيزيح جميع العناصر متقدماً مثل الفقاعة إلى أن يحتل مكانه الحقيق و هو آخر عنصر بالمصفوفة.

شفرة جافا لخوارزمية الترتيب الفقاعي

public static int[] bubblesort(int[] numbers) {
    boolean swapped = true;
    for(int i = numbers.length - 1; i > 0 && swapped; i--) {
        swapped = false;
        for (int j = 0; j < i; j++) {
            if (numbers[j] > numbers[j+1]) {
                int temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = temp;
                swapped = true;
            }
        }
    }
    return numbers;
}

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

شرح خوارزمية الترتيب بالإدخال [سطر سطر]

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

الشجرة البيانية من أهم مفاهيم الخوارزميات


قد يعجبك أيضا

ما رأيك؟ اترك تعليقاً أدناه


  1. السلام عليكم اخي الاستاذ مصطفى هل من الممكن ان تقدم لنا شرحاً عن المكدسات في هياكل البيانات و شكرا

{"email":"البريد الالكتروني غير صحيح","url":"رابط الموقع غير صحيح","required":"بعض الحقول المطلوبة لم تتم تعبئتها"}

نجاح!

تنبيه!

خطأ!