خوارزمية البحث الثنائي في JavaScript: دليل شامل للمطورين

مقدمة إلى عالم الخوارزميات والبحث الثنائي

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

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

ماذا ستتعلم في هذا الدليل؟

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

• مفهوم البحث الثنائي (Binary Search)
• ترميز Big O Notation لوصف أداء الخوارزميات
• الكود الأمرّي (Imperative Code) في تطبيق الخوارزميات
• البرمجة العودية (Recursion)
• العودية الذيلية (Tail Recursion)
• تقسيم المصفوفات (Array Splitting)
• عرض المصفوفات (Array View)
• تقسيم البيانات (Partition)

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

• المفهوم النظري (Walkthrough): تقديم الخوارزمية من منظور مفاهيمي.
• التطبيق العملي (Implementation): بناء نسخ خاصة بنا من الخوارزمية.
• المقارنة والحل (Solution): عرض تطبيق احترافي للمقارنة والتعلم.

المتطلبات الأساسية

لتحقيق أقصى استفادة من هذا الدليل، يُفضل أن يكون لديك فهم جيد للغة JavaScript. إذا كنت مطورًا حاليًا أو خريجًا من معسكر تدريبي (Bootcamp)، فستجد هذا المحتوى ذا قيمة كبيرة. أما إذا لم تكن قد وصلت إلى هذا المستوى بعد، فننصحك بمراجعة أساسيات JavaScript و ES6+.

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

تُعد خوارزمية البحث الثنائي واحدة من الاستراتيجيات الفعالة للإجابة على السؤال: "أين يظهر هذا العنصر في القائمة؟". قبل الغوص في تفاصيلها، دعنا نفهم مفهوم Big-O notation، وهو وسيلة لوصف أسوأ أداء محتمل للخوارزمية.

ترميز Big O Notation

يصف ترميز Big O Notation مدى كفاءة الخوارزمية من حيث الوقت والمساحة. على سبيل المثال، يشير Big O من O(n) إلى أنه إذا كانت المصفوفة تحتوي على n عنصرًا، فسيكون وقت التشغيل متناسبًا مع n. بمعنى آخر، ستستغرق مصفوفة مكونة من سبعة إدخالات سبع عمليات بحث في أسوأ الأحوال، تمامًا كما ستستغرق مصفوفة مكونة من سبعة ملايين إدخال سبعة ملايين عملية بحث في أسوأ الأحوال. يُمكننا القول أيضًا أن وقت تشغيل هذه الخوارزمية خطي.

مقارنة بين أساليب البحث: Sweeper و Splitter

عند البحث عن عنصر في قائمة، هناك طريقتان رئيسيتان:

• طريقة المسح (Sweeper): تتضمن فحص كل عنصر في القائمة بالتسلسل حتى يتم العثور على العنصر الصحيح.
• طريقة التقسيم / البحث الثنائي (Splitter / Binary Search): تتضمن تقسيم القائمة إلى النصف، والتحقق مما إذا كنت قد تجاوزت العنصر المطلوب أو لم تصل إليه بعد، ثم البحث في الجانب الأيمن أو الأيسر على التوالي، وتكرار العملية حتى يتم تحديد موقع العنصر.

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

يُعد البحث الثنائي أكثر كفاءة من طريقة المسح، خاصة للقوائم الكبيرة، ولكنه يعمل فقط عندما تكون القائمة مرتبة مسبقًا. بينما تتمتع طريقة المسح بوقت تشغيل خطي (O(n))، فإن طريقة التقسيم (البحث الثنائي) تتمتع بوقت تشغيل شبه خطي و Big O من O(log n)، مما يعني أداءً أفضل بكثير مع تزايد حجم البيانات.

تطبيقات مختلفة للبحث الثنائي

1. التنفيذ بالطريقة الأمرية (Imperative)

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

2. استخدام البرمجة العودية (Recursion)

لتحسين أداء البحث الثنائي وجعل الكود أكثر قابلية للقراءة، يُمكننا تطبيق نسخة جديدة باستخدام البرمجة العودية (Recursion) ودون استخدام الحلقات التكرارية. يجب تهيئة جميع المتغيرات باستخدام المعامل const لضمان عدم قابليتها للتغيير (immutability). إليك الهيكل الأساسي للحل:

let binarySearchWithRecursion = ( array, element, compare = defaultCompare ) => {
    return -1 ;
};

export default binarySearchWithRecursion;

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

3. تحسين العودية باستخدام Tail Recursion

التحدي التالي يهدف إلى تحسين تطبيقنا السابق عن طريق تقليل التكرار في الكود. يُحذر الخبراء من أن الحل قد يبدو أسوأ من الحلين السابقين في البداية، ومع ذلك، فإنه يمهد الطريق لتحسينات أفضل في المستقبل. تُعد Tail Recursion تقنية لتحسين الأداء في اللغات التي تدعمها، حيث يتم تحويل الاستدعاءات العودية إلى حلقات تكرارية لتجنب تجاوز مكدس الاستدعاءات (stack overflow).

4. تقسيم المصفوفات (Array Splitting)

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

لمساعدتنا في تحقيق ذلك، إليك بعض الكود الهيكلي:

let binarySearchWithArraySplitting = ( array, element, compare = defaultCompare ) => {
    return -1 ;
};

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

5. استخدام عرض المصفوفة (Array View)

في هذا القسم، نبحث عن طرق لدمج الأداء العالي لحلولنا السابقة مع أناقة طريقة array splitting. لتحقيق ذلك، نقوم بإنشاء كائن شبيه بالمصفوفة (array-like object) يستجيب لنفس طرق المصفوفة. ثم نقوم بحقن هذا الكائن بدلاً من المصفوفة الأصلية.

يبدأ الحل بتهيئة دالة ArrayView التي تُرجع كائنًا يتوقع ثلاث وسائط: array و start و end. عند استدعائها، يجب أن تُرجع ArrayView كائنًا بأربع طرق: length و toArray و slice و get.

export let ArrayView = ( array, start = 0 , end = array.length, ) => ({
    length : end - start,
    toArray : () => array.slice(start, end),
    slice : () => ,
    get: () => ,
});

let binarySearchWithArrayView = ( array, ...args ) => binarySearchWithArraySplitting(ArrayView(array), ...args)

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

6. تقسيم المصفوفة (Array Partition)

في التحدي الأخير، نهدف إلى استخلاص بعض المنطق المعقد (bounce logic) في نسختنا السابقة إلى بنية بيانات. لهذا، نحتاج إلى بنية بيانات بسيطة تُرجع الجزء الأوسط أو الأيسر أو الأيمن من المصفوفة. للبدء، نقوم بإعداد دالة ArrayPartition:

export let ArrayPartition = ( array, pivot ) => ({
    left : () => array.slice( 0 , pivot),
    middle : () => array.get(pivot),
    right : () => array.slice(pivot + 1 , array.length),
});

بعد ذلك، يتم إعداد نسخة جديدة من البحث الثنائي تُسمى binarySearchWithPartition، والتي لها نفس التوقيع الأولي لـ binarySearchWithArraySplitting:

let binarySearchWithPartition = ( array, element, compare = defaultCompare ) => {
    if (array.length === 0 ) {
        return -1 ;
    }
    const middle = Math .floor(array.length / 2 );
    const comparison = compare(element, array.get(middle));
    if (comparison === 0 ) {
        return middle;
    }
    //bounce logic
    const [left, right] = comparison === -1 ? [ 0 , middle - 1 ] : [middle + 1 , array.length];
    //end of bounce logic
    const subIndex = binarySearchWithArraySplitting( array.slice(left, right), element, compare );
    return subIndex === -1 ? -1 : left + subIndex;
};

let binarySearchWithPartitionAndView = ( array, ...args ) => binarySearchWithPartition(ArrayView(array), ...args);

التحدي الآن هو إعادة كتابة binarySearchWithPartition بدون أي من منطق bounce logic الموضح أعلاه، وبدلاً من ذلك، إنشاء تقسيم للمصفوفة وإجراء استدعاءات لطرقها left و middle و right. هذا التحدي قد يكون صعبًا، لذا لا تتردد في مراجعة الحل النموذجي إذا واجهت صعوبة.

الخلاصة التقنية

لقد استعرضنا في هذا الدليل رحلة متكاملة مع خوارزمية البحث الثنائي في JavaScript، بدءًا من مفاهيمها الأساسية وصولًا إلى تطبيقاتها المتقدمة. تعلمنا أن البحث الثنائي يُعد أداة قوية وفعالة للغاية للبحث في القوائم المرتبة، حيث يوفر أداءً زمنيًا لوغاريتميًا (O(log n)) يتفوق بكثير على البحث الخطي (O(n)) مع تزايد حجم البيانات.

استكشفنا مجموعة متنوعة من الأساليب لتطبيق هذه الخوارزمية، من التنفيذ الأمري البسيط إلى استخدام البرمجة العودية، مرورًا بتقنيات تحسين مثل Tail Recursion، وابتكارات مثل Array Splitting و Array View، وصولًا إلى هيكلة البيانات المتقدمة باستخدام Array Partition. كل طريقة قدمت مزايا وعيوبًا خاصة بها، سواء من حيث الأداء أو استهلاك الذاكرة أو قابلية قراءة الكود.

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