خوارزميات البحث و الترتيب (الجزء الرابع)

هذه المشاركة سأضع فيها الحل بعد انتهاء النقاش.

:: تعديل ::

تمت إضافة الحل.

لإيجاد مكان المفتاح في المصفوفة, نبحث عن رقم السطر الذي يحوي قيمة المفتاح ثم نُطبق عليه خوارزمية البحث الثنائي, مع الأخذ في الاعتبار أن المصفوفة مُرتبة حسب الأعمدة و الصفوف أيضا:

#include <iostream>
using namespace std;

#define numberOfColumns 4

bool searchTwoDimensional(int array[][numberOfColumns], int rows, int columns, int value) {
    int i = 0;
    while (i <= rows - 1 && array[i++][0] <= value);
    if (i == 0) return false;
    else {
        i--;
        int low = 0, high = columns - 1, mid = (low + high) / 2;
        while (array[mid] != value && low <= high) {
            array[mid] < value ? low = mid + 1 : high = mid - 1;
            mid = (high + low) / 2;
        }
        if (high < low) return false;
        else return true;
    }
}

int main() {
    int newArray[3][numberOfColumns] = {
        {1, 3, 5, 7},
        {10, 15, 27, 28},
        {30, 39, 52, 100}
    };
    cout << searchTwoDimensional(newArray, 3, numberOfColumns, 52);
    return 0;
}

بعد الخروج من الحلقة الأولى, لدينا ثلاث حالات:

• i=0 و هذا يعني أنه لم يتم الدخول إلى الحلقة ! لأن قيمة أول عنصر في المصفوفة أكبر تماما من قيمة المفتاح. و بما أن المصفوفة مرتبة حسب الأعمدة و الصفوف, فيمكننا القول بأن المفتاح غير موجود في المصفوفة. في هذه الحالة ستعيد الدالة false.
  
• i أكبر أو يساوي 2 و أقل أو يساوي rows, في هذه الحالة سيمثل i رقم أول سطر يبدأ بقيمة أكبر تماما من قيمة المفتاح, لذا فإن المفتاح سيتواجد في السطر رقم i-1.
  
• i = rows + 1, هذه الحالة تعني أن جميع الأسطر تبدأ بقيمة أكبر تماما من قيمة المفتاح , قد يتواجد المفتاح في السطر الأخير من المصفوفة.

بعد الخروج من الحلقة الأولى (في حالة i يختلف عن الصفر), سيتنقل التنفيذ إلى الجزء المخصص للبحث عن قيمة المفتاح باستخدام خوارزمية البحث الثنائي. (راجع الحلقة السابقة إن لم تفهم هذا الجزء)

في الدالة الرئيسية, قمنا بالإعلان عن مصفوفة ثنائية البعد, تحتوي على 3 أسطر و أربعة أعمدة. ثم قمنا بالبحث عن القيمة 52 التي تتواجد في آخر أسطر المصفوفة.

بالنسبة للتعقيد الزمني :

في أسوأ الحالات, ستمر الحلقة الأولى على جميع أسطر المصفوفة و بالتالي سيكون تعقيدها الزمني من النوع

الحلقة الثانية لها تعقيد لوغاريتمي

إذا, التعقيد الكلي سيكون

لا يمكننا تبسبط هذه العبارة لأننا لا نعرف العلاقة ما بين rows و columns.

أنا في الخدمة, أي سؤال ؟ :)