اقرأ في هذا المقال
سواء كنت تبحث في قائمة تشغيل لأغنيتك المفضلة أو تبحث من خلال قائمة لاختيار المطعم لتناول وجبتك التالية، فإن حياتنا مليئة بالبحث عن الأشياء، بالطريقة نفسها تمامًا، تقوم أجهزة الكمبيوتر بإجراء استعلامات بحث عن مجموعات البيانات وهياكلها، ومع ذلك على عكس البشر يتعين على أجهزة الكمبيوتر إجراء عمليات البحث على مجموعات بيانات أكبر بكثير، وفي أوقات تكون فيها أسرع من البشر، حيث دفع هذا علماء الكمبيوتر إلى ابتكار العديد من خوارزميات البحث، حيث يكون كل منها عادةً أفضل من بعض الخوارزميات الأخرى في مجموعات معينة.
مفهوم خوارزمية البحث بالقفز:
خوارزمية البحث بالقفز (Jump Search) ويشار إليها أيضًا باسم خوارزمية البحث بالكتل (Block Search)، وهي خوارزمية تُستخدم للبحث عن موضع عنصر الهدف في مجموعات أو هياكل البيانات المرتبة، بدلاً من البحث في المصفوفة عنصرًا تلو الآخر (كما في خوارزمية البحث الخطي)، باستخدام خوارزمية البحث بالقفز، يتم تقسيم مجموعة البيانات التي تم ترتيبها إلى مجموعات فرعية من العناصر، تسمى بالكتل (blocks).
ثم تقوم خوارزمية البحث بالقفز بتقييم العنصر ذو أعلى قيمة في كل كتلة، بدلاً من تقييم تقييم جميع العناصر، وذلك لأن المصفوفة مرتبة، إذ تقوم الخوارزمية بإيجاد مفتاح البحث (وهي القيمة التي يتم البحث عنها) من خلال مقارنة مرشح البحث في كل كتلة، عندما يتم ترتيب المصفوفة، يكون مرشح البحث هو أعلى قيمة في الكتلة، لذلك عند مقارنة مفتاح البحث مع مرشح البحث، يمكن للخوارزمية القيام بأحد الأشياء الثلاثة:
1- إذا كان مرشح البحث أقل من مفتاح البحث، فسنقوم بفحص الكتلة التالية.
2- إذا كان مرشح البحث أكبر من مفتاح البحث، فسنجري بحثًا خطيًا على الكتلة الحالية.
3- إذا كان مرشح البحث هو نفسه مفتاح البحث، فقم بإرجاع المرشح.
يتم اختيار حجم الكتلة كجذر تربيعي لطول المصفوفة، لذلك، فإن المصفوفات ذات الطول (n) لها حجم كتلة (n√)، حيث يوفر هذا في المتوسط أفضل أداء لمعظم المصفوفات، ومن خلال الانتقال المتكرر، أو بالأحرى القفز للأمام، سنجد العنصر الهدف أو سنصل إلى نهاية المجموعة دون العثور عليه.
شرح آلية عمل خوارزمية البحث بالقفز:
دعونا نفرض أن لدينا المصفوفة المرتبة التالية، ونبحث عن عنصر في المصفوفة من خلال النظر في حجم الكتلة:
دعونا نفرض أننا نقوم بالبحث عن الرقم (10) في المصفوفة أعلاه، وقد تم ترتيب المصفوفة ، وهي تلبي متطلباتنا لاستخدام الخوارزمية، نظرًا لأن هذه مصفوفة صغيرة، ستقوم الخوارزمية بتحديد حجم كتلة البحث بـ (2)، الآن، تبدأ الخوارزمية بالبحث من البداية وتبحث عن العنصر الهدف، من البداية، الكتلة الأولى تحتوي على العنصرين الأول والثاني (5, 2)، نظرًا لأن مرشح البحث (5) أقل من مفتاح البحث (أي أنه غير متواجد في هذه الكتلة)، إذاً سينتقل البحث إلى الكتلة الثانية
تنتقل الخوارزمية للبحث في الكتلة الثانية، والتي تحتوي على العنصرين (8, 7)، إذ أن مرشح البحث (8) أقل من عنصر الهدف (10)، نظرًا لذلك فإن العنصر الهدف لا يقع في هذا النطاق، فينتقل البحث إلى الكتلة الثالثة.
الآن، ينتقل البحث إلى الكتلة الثالثة والتي تحتوي على العنصرين (12, 10)، نظراً لأن مرشح البحث (12) أكبر من عنصر الهدف (10) يتم عمل بحث خطي للعثور على مكان العنصر الهدف.
تعقيد الوقت لخوارزمية البحث بالقفز:
يقع التعقيد الزمني لخوارزمية البحث بالقفز بين خوارزمية البحث الخطي “O (n)” وخوارزمية البحث الثنائي “O (Log n)”، تُعد خوارزمية البحث الثنائي أفضل من خوارزمية البحث بالقفز، ولكن ميزة خوارزمية البحث بالقفز هي أننا ننتقل للخلف مرة واحدة فقط (وقد يتطلب البحث الثنائي قفزات تصل إلى “O(Log n)”)، افرض أن طول المصفوفة هو (n) و حجم المصفوفة هو (m):
- في أفضل الأحوال: ستجد خوارزمية البحث بالقفز العنصر الهدف على حافة الكتلة الأولى التي يبحث فيها، يتسبب هذا في أن أفضل حالة لتعقيد “O(1)” .
- في أسوأ الأحوال: فإن خوارزمية البحث بالقفز ستقفز على التوالي إلى آخر كتلة بحثًا عن العنصر الهدف، مما يتسبب بدوره في حدوث عدد من القفزات (n/m)، بالإضافة إلى ذلك، إذا كانت قيمة العنصر الأخير لهذه الكتلة أكبر من العنصر الهدف، فإن الخوارزمية ستقوم ببحث خطي بتكرارات (m-1)، وفقًا لذلك، تستغرق خوارزمية البحث بالقفز في أسوء الأحوال والمتوسطة لتعقيد “O(√n)”.
