[CPCS 204] الدرس الثاني: Searching Techniques

[deathpain]

-----------------------------------------------

بسم الله الرحمن الرحيم
السلام عليكم ورحمة الله وبركاته

" العلم كالأرض لا يمكننا أن نمتلك منه سوى القليل " .. المفكر الفرنسي فولتيـر

-----------------------------------------------

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


------------
~l| البحث الخطي |l~
------------

سبق وأن درسنا في مادتي البرمجة 202 و 203 كيفية البحث عن البيانات داخل الـArrays وكانت الطريقة بسيطة وبدائية إلى حد ما، فكان يجب علينا البحث داخل عناصر المصفوفة عنصراً عنصراً وإذا وجدنا العنصر نخرج من اللوب الخاصة بالبحث، وإذا لم نجد العنصر فإننا في كل حال سنمر على كامل عناصر المصفوفة، أي إذا كان لدينا مصفوفة تتكون من 1000 عنصر فإنه بإنتهاء البحث سنمر على الـ1000 عنصر كاملة .

كود PHP:

public static int LinearSearch(int[] array, int value){

for (int i=0;i<array.length;i++){

if (a[i] == value )
return 1;

} \\ End of Loop
 return 0;

} \\ End of Method 


عندما استخدامنا للبحث الخطي Linear Search في السابق كانت هذه الطريقة هي المثلى والرائعة والأفضل وهي كذلك في حال كانت المصفوفة غير مرتبة ( Unsorted ).

ولكن لنسأل أنفسنا سؤالاً:
ماذا لو كانت المصفوفة مرتبة ( Sorted )، هل سيمكننا البحث عن العناصر بطريقة أفضل ؟

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

في هذه اللعبة أغلب الأشخاص سيختارون الاختيار 50 كأول اختيار لهم، لماذا ؟
لأنهم بهذا قسمو عدد الاحتمالات إلى النصف فإما أن تكون في النصف العلوي 50-100 أو النصف السفلي 1-49 ،،
أفضل طريقة للفوز باللعبة دائماً هي بتقليص عدد الاحتمالات إلى النصف 50 - 25 - 12 - 6 - 3 - 1 وهكذا

السؤال هنا: هل يمكنني الاستفادة من فكرة هذه اللعبة في البحث عن البيانات داخل المصفوفة ؟
ستعرفون إجابة هذا السؤال من التالي

------------
~l| البحث الثنائي |l~
------------
لنفرض أن لدينا هذه المصفوفة المرتبة من الأصغر للأكبر:


ولنفرض أننا نريد البحث عن العنصر الذي يحمل القيمة 19، عادة كنا سنذهب إلى أول عنصر وآخر عنصر ونجمعهما ونقسمها على 2 وسنحصل في هذه الحالة على الرقم 60، وعندما نأتي للمصفوفة لا نجد الرقم 60، وحتى أقرب رقم للـ60 يقع في الخانة قبل الأخيرة.

ولكن ماذا لو أخذنا فكرة اللعبة السابقة في هذا المثال ؟
أول Index في المصفوفة هو 0 وآخر Index في المصفوفة هو 8، لذا سنجمعهما ونقسمهما على 2 وعندها سيكون المنتصف هو الـIndex رقم 4.
وسندع الكمبيوتر يتأكد هل القيمة الموجودة في Index رقم 4 أكبر من 19 أو أصغر منه ؟
الـIndex رقم 4 يحمل القيمة 33 وهي في هذه الحالة أكبر من 19 وهذا يعني أننا قللنا مجال البحث وحصرناه بين Index رقم 0 و Index رقم 3 ! وسيتم تعديل خاصية البحث لتصبح من 0 إلى 3، وعندها سنضطر إلى جمع 0 والـ3 ونقسمهما على 2 لنحصل على 1 ثم نذهب إلى الـIndex رقم 1 ونتأكد من قيمته ونجد أنها 6 فهذا يعني أن الرقم 19 سيكون ما بين الـIndex 2 و الـIndex 3 ،، وعندها نجمع 2 + 3 ونقسمها على 2 لنحصل على 2 ووجدنا عندها الـ19 ..

( ملاحظة: جميع العمليات هنا تنطبق عليها خواص الـIntegers، فيعني أن 2 + 3 عند قسمتهما على 2 نحصل على 2 وليس 2.5 )

فلو لاحظنا في المسألة أن الشيء الوحيد الذي يتغير هوا مجال البحث ففي البداية كان بين 0 و 8، ثم أصبح بين 0 و 3 وبعدها أصبح بين 2 و 3 ..

كود توضيحي للطريقة:

كود PHP:

public static int BinarySearch( int[] array, int value){
int low =0;
int high = array.length;
while ( low < high ) {
int mid = ( low + high ) / 2;
if (array[mid] == value)
return 1;

else if (array[mid] < value)
low = mid + 1;

else 
high = mid - 1;
} End of While Loop

return 0; 
} End of Method 


الـLow هنا يمثل رقم أول Index يبدأ البحث عنده والـHigh هو رقم آخر Index والـMid هنا يمثل طريقة التخمين بأخذ نصف الحيز الموجودة لدينا.

نلاحظ في هذه الطريقة تميز البحث الثنائي BinarySearch على البحث الخطي LinearSearch حيث أن عدد مرات التأكد أصبح أقل بكثير وبطريقة مميزة !

لنجري بعض المقارنات عن أسوأ حالة لكل من الطريقتين:
لنفرض أن لدينا مصفوفة بها 100 عنصر، ونريد البحث عن عن غير موجود بها، كم عدد مرات التخمين أو التأكد من العناصر سيقوم بها كل من الحالتين.

في الـ LinearSearch إذا كان العنصر غير موجود فأنه سيقوم بالتأكد من 100 عنصر أي 100 عملية تأكد.
أما في الـ BinarySearch فإنه سيقوم بالتالي:
* في التخمينة الأولى سيقلل مجال البحث إلى 50 عنصر
* في التخمينة الثاني سيقلل مجال البحث إلى 25 عنصر
* في التخمينة الثالثة سيقلل مجال البحث إلى 12 عنصر
* في التخمينة الرابعة سيقلل مجال البحث إلى 6 عناصر
* في التخمينة الخامسة سيقلل مجال البحث إلى 3 عناصر
* في التخمينة السادسة سيقلل مجال البحث إلى عنصر واحد
* في التخمينة السابعة لن يبقى أي عنصر للتأكد منه وسيخرج من الميثود

نلاحظ هنا التفوق التام للـBinarySearch بـ7 محاولات للتأكد مقابل 100 محاولة للـLinearSearch !!

حالة عامة للـBinarySearch وطريقة حسابها:
* في المرة الأولى سيكون عدد العناصر المتبقية يساوي n/2^1
* في المرة الثانية سيكون عدد العناصر المتبقية يساوي n/2^2
* في المرة الثالثة سيكون عدد العناصر المتبقية يساوي n/2^3
* في المرة الرابعة سيكون عدد العناصر المتبقية يساوي n/2^4
* في المرة k سيكون عدد العناصر المتبقية يساوي n/2^k
وهكذا .. ( n تمثل في المثال السابق عدد العناصر كاملاً وهو 100 ) ..

نحن نريد الحصول على عنصر واحد فقط عند البحث، لذا ستكون المعادلة كالآتي:
n/2^k = 1
نضرب الطرفين في 2^k فتصبح:
n = 2^k
وبأخذ الـlog الطبيعي لها نحصل على:
k = log(2) n

فهذا يعني أن الوقت التي تستغرقه عملية البحث عن عنصر بواسطة BinarySearch تستغرق Log n من الوقت عكس الـLinearSearch الذي يستغرق n من الوقت.

وختاماً سأقوم بعرض عدد المحاولات التي يقوم بها الـBinarySearch على عدد من الأرقام:
* مصفوفة حجمها 8، ينتهي منها في 3 محاولات فقط
* مصفوفة حجمها 1024، ينتهي منها في 10 محاولات فقط
* مصفوفة حجمها 65536، ينتهي منها في 16 محاولة فقط
* مصفوفة حجمها 1048576، ينتهي منها في 20 محاولة فقط
* مصفوفة حجمها 33554432، ينتهي منها في 25 محاولة فقط
* مصفوفة حجمها 1073741824، ينتهي منها في 30 محاولة فقط

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

تم بحمد الله