خوارزميات البحث تلعب دوراً هاماً في العديد من البرامج. ربما نحتاج البحث عن شي في قاعدة بيانات، أو نريد معرفة ما أذا كان شيئ موجود بالفعل في صفيف (Array).
غالباً في برامجنا سنطبق خوارزميات البحث على Array، كما في هذا المقال، لذلك من المناسب البدء بمقدمة على ال Arrays.
ما هي المصفوفات (Arrays)؟
للبدء تخيل انك تريد ان تبني قائمة لكل تغريداتك على تويتر. ستريد ان تخزنها بطريقة ما (لكي يكون لذى صفحتك على تويتر المعلومات لعرض تغريداتك). بسداجة من امكانك بدء انشاء متغيرات (Variables) لحفض كل تغريدة على حدى.
FirstTweet = "my First tweet!"
Second tweet = "second tweet..."
Third tweet = "I'm getting bored"لكن ستجد سريعا أن هذه الطريقة تؤدي الى عمل شاق. بالإضافة الى العدد الا متناهي من المتغيرات و عدم وجود ما يربط التغريدات ببعضهم. المصفوفات تجعل هذه العملية اكثر سلاسة.
المصفوفات تحتوي على مجموعة مرتبة من البيانات التي يمكن الوصول اليها من خلال مؤشر عدد صحيح.
يمكن للمصفوفات الإحتواء على عدد من أنواع عديدة من البيانات، ليس أرقام فقط.
هناك بعض الأمور التي يجب مراعاتها بشأن المصفوفات:
- في المثال السابق نرى أن المصفوفة لديها حجم 6. عندما تمتلئ المصفوفة يمكننا إضافة بند إلا إذا غيرنا حجم المصفوفة أو إذا قمنا بإزالة بند.
- يمكنك أيضا أن ترى أن كل حاوية مربوطة برقم، الذي يسمى بمؤشر (index). بواسطة هذه الأرقام يمكن للمبرمج أن يصل إلى موقع بند ما، ما يجعلها فعالة جدا.
في العادة يبدء المؤشر برقم 0، و هو أمر يربك الكثير من المبتدئين في البداية.
//Examples:
Array[0] = 1
Array[3] = 6
Array[8] = 14
...أحد العمليات المفيدة التي يمكننا أن نفعلها مع المصفوفات هي البحث.
البحث الخطي – Linear Search
البحث الخطي أبسط خوارزميات البحث حيث أنها الطريقة التي نستخدمها غالبا في حياتنا اليومية.
تخيل أنك تريد أن تبحث في قائمة تحتوي على 1000 إسم لو الإسم أكرم موجود فيها، فتبدأ بالذهاب خلال القائمة، بالتسلسل و تحقق ما إذا كان الإسم يطابق أكرم لكل عنصر في المصفوفة. هذا يسمى بالبحث الخطي. في أسوأ حال، عندما الإسم الذي نبحث عليه يكون في آخر القائمة, يجب أن نمر خلال 1000 عنصر، هذا ما يعطي تسمية “خطي” لهذه الخوارزمية و ما يجعلها غير فعالة في أغلب الأحوال.
هل يمكننا أن نفعل أفضل من هذا؟
من أول نضرة نشعر بأن هذا صعب – كما لقائمة من البيانات الغير مرتبة – ليست هناك علاقة ما بين البيثانات فيجب علينا المرور خلالها بالكامل لنجد شيئ.
لكن ما إذا كانت البيانات مرتبة؟
البحث الثنائي – Binary Search
نحدد المقارنة بعملية تأخد رقم و تعطينا ما إذا كان الرقم أكبر، يساوي أو أصغر من رقم آخر.
تخيل أن لدينا قتائمة مرتبة من الأرقام و نريد أن نعرف لو الرقم 3 موجود فيها. نعرف أن الأرقام في القائمة مرتبة من الأصغر إلى الأكبر، من اليسار إلى اليمين. نأخد الرقم الذي في نصف المصفوفة تقريباً، و هو الرقم الخامس و الموجود في الخانة 4. هذا الرقم 7 و ليس الرقم الذي نبحث عليه، و لكن نعرف أن الرقم 3 أصغر من الرقم 7، و أن كل الأرقام على يمين الرقم 7 أكبر منه؛ لذلك يمكننا البحث في الجزء على اليسار من الرقم 7 فقط و ذلك من الخانة 0 إلى الخانة 4، لأنه يحتوي على الأرقام الأصغر من أو تساوي 7.
ألآن نختار الرقم 4 الذي في نصف المصفوفة و نرا أن 3 أصغر من أربعة، فنأخذ بعين ألإعتبار الخانات من 0 إلى 1، ألآن لدينا رقمين فقط فنرى أن 1 أصغر من 3 و لكن الرقم الثاني يساوي 3. وجدنا رقم 3 في المصفوفة في الخانة رقم 1.
بكلمات بسيطة، البحث الثنائي يختار مراراً و تكراراً الرقم وسط جزء الباقي من المصفوفة و يقرر ما إذا كان الرقم على يمين أو على يسار الرقم المختار (أو الرقم المختار بالضبط). في كل تكرار تقسم الأرقام المتبقية إلى قسمين و ذلك يجعل البحث الثنائي فعال جداً لأنه يقلل من عدد العمليات التي يجب على الحاسوب فعلها، و خصوصاً في المصفوفات الطويلة.
في النهاية يمكننا أن نلخص الأمر بالشكل التالي: إذا كانت القائمة مرتبة من الأفضل إستخدام البحث الثنائي لفعاليته، العالية، أما إذا كانت القائمة غير مرتبة فيجب المرور خلال كل القائمة حتى نجد الشيئ الذي نبحث عنه، يعني إستخدام البحث الخطي.