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

بسم الله الرحمن الرحيم 

لقد تحدثنا في المقال السابق عن خوارزمية البحث الخطي، وذكرنا أنّ درجة تعقيد الخوارزمية من المرتبة O(n) أي تعقيد خطي. لكن ماذا لو كان عدد العناصر التي يجب البحث ضمنها كبيرًا؟ سيكون تعقيد الخوارزمية كبيرًا! وماذا لو أنّ العناصر مرتبةٌ ضمن مصفوفة البحث؟ ألا يجب أن نستغل هذه الميزة لتحسين البحث؟!

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

خوارزمية البحث الثنائي هي خوارزمية بحثٍ تعمل على مبدأ فرّق تَـسُد! بحيث تكون عناصر مصفوفة البحث مرتبةٌ ترتيبًا تصاعديًا أو تنازليًا، وإن لم تكن مرتبةً يجب أن نقوم بترتيبها بطريقةٍ ما،  فلنرَ كيف تعمل!

خوارزمية البحث الخطي – Linear Search

لفهم مدى فعالية الخوارزمية، دعونا نتخيل لو تمّ ترتيب جميع الأسماء الموجودة في العالم بترتيبٍ أبجدي، وقمنا بالبحث عن اسمٍ معينٍ موجود بين هذه الأسماء، ستقوم هذه الخوارزمية بإيجاد موقع الاسم فقط ضمن 35 عملية بحثٍ على الأكثر.

ما هي آلية عمل الخوارزمية؟

تبدأ الخوارزمية بتحديد دليل العنصر الذي يقع في وسط المصفوفة حتى تقسم المصفوفة إلى قسمين (هنا يتبيّن مبدأ فرق تسد).

مثال عملي لتوضيح آلية العمل:

فلنفترض وجود مصفوفة (Arr) تحتوي على الأعداد من صفر إلى 9:

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

لكن إنْ استخدمنا خوارزمية البحث الثنائي سيتم إنجاز المطلوب خلال وقت أسرع وزمن تعقيد أقل، فلنختبر الخوارزمية عن طريق البحث عن الرقم 3 على سبيل المثال:

علينا بدايةً تحديد موقع (دليل) العنصرين الأول والأخير في المصفوفة على النحو الآتي:

Low = 0

High = n-1

بعدها نقوم بحساب دليل العنصر الذي يقع في منتصف المصفوفة وليكن mid وذلك عن طريق جمع Low و High وتقسيم الناتج على 2:

ونتحقق من أنّ العنصر الذي دليله mid أكبر أم أصغر من القيمة التي نبحث عنها، وبما أننا نعمل دومًا على أعداد مرتبة، لذلك إذا كان العنصر الذي دليله mid أصغر سنقوم بتغيير قيمة الـدليل Low إلى الـ (mid+1) أو إذا كانت أكبر سنقوم بتغيير قيمة الـدليل High إلى (mid-1)، إذْ أننا في كل مرةٍ نقوم بتقسيم المصفوفة إلى قسمين، والبحث في القسم الذي نكون متأكدين من وجود العدد الذي نبحث عنه فيه.

طبعا نزيد أو ننقص واحد من القيمة بسبب وجود شرطٍ آخر، هو أنه لو كانت القيمة متساوية نقوم بطباعة الرقم، غير ذلك نحن لسنا بحاجة لموقع الـ high أو الـ Low الأصلي لأنه ليس مطابقًا للقيمة التي نبحث عنها.

مثال برمجي لتوضيح الخطوات:

	int binarySearch(int low,int high,int key)
	{
	while(low<=high)
	{
	int mid=(low+high)/2;
	if(a[mid]<key)
	{
	low=mid+1;
	}
	else if(a[mid]>key)
	{
	high=mid-1;
	}
	else
	{
	return mid;
	}
	}
	return -1; //key not found
	}

view rawbinary-search.cpp ❤by Excellent  Programmer 

زمن تعقيد الخوارزمية (Time Complexity)

الزمن اللوغاريتمي هو اللوغاريتم الثنائي للعدد Log(n)، وذلك لأنه في كل مرةٍ نقوم بتقسيم مجال البحث إلى قسمين