البحث
ستكون العملية التالية التي سأكتبها هي findCard، التي ستبحث في مصفوفة أوراق لترى إذا كانت تحتوي على ورقة معينة. ستعطيني هذه العملية الفرصة لأشرح خوارزميتين: البحث الخطي (linear search) والبحث المجزّأ (bisection search).
البحث الخطي واضح للغاية؛ نجتاز مجموعة الورق ونقارن كل ورقة بالورقة التي نبحث عنها. إذا عثرنا عليها نعيد الدليل الذي تظهر عنده الورقة. إذا لم تكن موجودة في مجموعة الورق، نعيد القيمة 1-.
كود:
public static int findCard(Card[] cards, Card card) {
for (int i = 0; i< cards.length; i++) {
if (sameCard(cards[i], card)) {
return i;
}
}
 
return -1;
}
متحولات العملية findCard هي card وcards. قد يبدو وجود متحول بنفس اسم النوع غريباً (المتغير card من النوع Card). يمكننا أن نميز بينهما لأن المتغير يبدأ بحرف صغير.
ترجع العملية بمجرد اكتشاف الورقة، ما يعني أننا لا نحتاج للمرور على مجموعة الورق بالكامل إذا وجدنا الورقة التي كنا نبحث عنها. إذا وصلنا إلى آخر الحلقة، سنعرف أن الورقة غير موجودة في المجموعة.
إذا لم تكن الأوراق في المجموعة مرتبة، لا توجد أي طريقة أسرع للبحث من هذه. علينا فحص كل ورقة لأننا لا نملك طريقة أخرى تمكننا من التأكد أن الورقة التي نبحث عنها ليست هذه الورقة.
لكن عندما تبحث عن كلمة في قاموس، فأنت لا تبحث عنها خطياً، لأن الكلمات مرتبة أبجدياً. ولذلك ستستخدم خوارزمية مشابهة لخوارزمية البحث المجزأ:
1. ابدأ في مكان ما في الوسط.
2. اختر كلمة في الصفحة وقارنها مع الكلمة التي تبحث عنها.
3. إذا وجدت الكلمة التي تبحث عنها، توقف.
4. إذا كانت الكلمة التي تبحث عنها تأتي بعد الكلمة الموجودة في هذه الصفحة، قلّب الصفحات إلى مكان لاحق في القاموس وانتقل إلى الخطوة 2.
5. إذا كانت الكلمة التي تبحث عنها تأتي قبل الكلمة الموجودة في هذه الصفحة، قلّب الصفحات إلى مكان سابق في القاموس وانتقل إلى الخطوة 2.
إذا وصلت إلى نقطة حيث توجد كلمتان متجاورتان في الصفحة وكان من المفروض أن توجد كلمتك بينهما، ستستنتج أن كلمتك غير موجودة في القاموس.
لنعد إلى مجموعة ورق الشدة، إذا علمنا أن الأوراق مرتبة، يمكننا كتابة نسخة أسرع من findCard. أفضل طريقة لكتابة البحث المجزأ هي باستخدام عملية تعاودية، لأن التجزئة تعاودية بطبيعتها.
الحيلة هي كتابة عملية باسم findBisect تأخذ دليلين كمعاملات، low وhigh، يشيران إلى القطعة من المصفوفة التي سيتم البحث فيها (تتضمن العنصر ذا الدليل low وكذا الدليل high).

  1. للبحث في المصفوفة، اختر دليلاً بين low وhigh (سمّه mid) وقارن العنصر الموافق له مع الورقة التي تبحث عنها.
  2. إذا عثرت عليها توقف.
  3. إذا كانت الورقة mid أعلى من الورقة التي تبحث عنها، ابحث في النطاق من low إلى mid-1.
  4. إذا كانت الورقة mid أدنى من ورقتك، ابحث في النطاق من mid+1 إلى high.

تبدو الخطوتين 3 و4 كاستدعاءات تعاودية مريبة. هذا ما ستبدو عليه هذه الخوارزمية بعد ترجمتها إلى شفرة Java:
كود:
public static int findBisect(Card[] cards, Card card, int low, int high) {
// TODO: need a base case
int mid = (high + low) / 2;
int comp = compareCard(cards[mid], card);
 
if (comp == 0) {
return mid;
} else if (comp > 0) {
return findBisect(cards, card, low, mid-1);
} else {
return findBisect(cards, card, mid+1, high);
}
}
هذه الشفرة تحتوي على لب البحث المجزأ، لكن تنقصها قطعة، ولذلك أضفت تعليق TODO (يلزم عمله).
كما هو مكتوب، ستظل العملية تستدعي نفسها للأبد إذا لم تكن الورقة موجودة في المجموعة. نحتاج إلى حالة قاعدية لمعالجة هذه الحالة.
إذا كان high أصغر من low، فلا توجد أوراق بينهما، كما ترى فقد استنتجنا أن تلك الورقة غير موجودة في المجموعة. إذا عالجنا هذه الحالة، ستعمل العملية بشكل صحيح:
كود:
public static int findBisect(Card[] cards, Card card, int low,
                                int high) {
     System.out.println(low + ", " + high);
 
     if (high < low) return -1;
 
     int mid = (high + low) / 2;
     int comp = cards[mid].compareCard(card);
 
     if (comp == 0) {
           return mid;
     } else if (comp > 0) {
           return findBisect(cards, card, low, mid-1);
     } else {
           return findBisect(cards, card, mid+1, high);
     }
}
أضفت تعليمة طباعة حتى أتمكن من متابعة تتابع الاستدعاءات التعاودية. لقد جربت الشفرة التالية:
كود:
Card card1 = new Card(1, 11);
System.out.println(findBisect(cards, card1, 0, 51));
وحصلت على الخرج التالي:
0, 51
0, 24
13, 24
19, 24
22, 24
23
ثم اخترعت ورقة غير موجودة في المجموعة (15 ديناري)، وحاولت العثور عليها. حصلت على ما يلي:
0, 51
0, 24
13, 24
13, 17
13, 14
13, 12
-1
هذه الاختبارات لا تثبت أن هذا البرنامج صحيح. في الواقع، لا توجد أية كمية من الاختبارات يمكن أن تبرهن أن برنامجاً ما يعمل بشكل صحيح. من جهة أخرى، بتجربة عدة حالات واختبار الشفرة، قد تقدر على إقناع نفسك بذلك.
عدد الاستدعاءات التعاودية نموذجياً 6 أو 7، لذا فنحن نستدعي compareCard 6 أو 7 مرات، مقارنة بما قد يصل إلى 52 مرة إذا اعتمدنا البحث الخطي. بشكل عام، البحث المجزأ أسرع بكثير من البحث الخطي، ويزداد فرق السرعة كلما ازداد حجم المصفوفة.
خطأين شائعي الحدوث في البرامج التعاودية هما نسيان تضمين حالة قاعدية أو كتابة الاستدعاء التعاودي بحيث لا يصل البرنامج للحالة القاعدية أبداً. كلا الخطأين سيسبب تعاوداً لانهائياً، الذي سيولد StackOverflowEception.