شرح خوارزمية البحث الخطي(Linear Search Algorithm)

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

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

مقدمة

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

قبل تعلم خوارزميات البحث المتقدمة مثل البحث الثنائي (Binary Search)، أو البحث المستند إلى التجزئة (hash-based lookup)، أو بحث الشجرة (tree search)، أو اجتياز الرسوم البيانية (graph traversal)، من المهم فهم البحث الخطي. يمثل البحث الخطي الطريقة الأكثر مباشرة للبحث: ابدأ من البداية وتحقق من كل عنصر حتى يتم العثور على الإجابة.

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

ما هو البحث الخطي؟

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

الفكرة الرئيسية بسيطة:

• ابدأ من العنصر الأول.

• قارن العنصر الحالي بالقيمة المستهدفة.

• إذا تطابقا، أعد الفهرس أو العنصر.

• إذا لم يتطابقا، انتقل إلى العنصر التالي.

• إذا وصل البحث إلى النهاية دون العثور على الهدف، أعد "غير موجود".

يُطلق على البحث الخطي اسم "خطي" لأن الخوارزمية تتحرك عبر البيانات في خط مستقيم، عنصرًا تلو الآخر.

لماذا البحث الخطي مهم

البحث الخطي مهم لأنه أبسط تقنية بحث. العديد من الخوارزميات الأكثر تقدمًا تكون أسهل في الفهم بعد تعلم كيفية عمل البحث الخطي.

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

على سبيل المثال، إذا كانت المصفوفة تحتوي على 10 عناصر فقط، فإن استخدام البحث الخطي قد يكون مقبولاً تمامًا. لا داعي لإضافة تعقيد إذا كان الحل البسيط واضحًا وموثوقًا وسريعًا بما يكفي للمشكلة.

كيف يعمل البحث الخطي

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

على سبيل المثال، إذا احتجنا إلى العثور على الرقم 7 في هذه المصفوفة:

[4, 2, 9, 7, 1]

تتحقق الخوارزمية من القيم بالترتيب:

Check 4 → not found
Check 2 → not found
Check 9 → not found
Check 7 → found

بمجرد العثور على الهدف، يمكن للخوارزمية التوقف فورًا. لا داعي للتحقق من القيم المتبقية.

مثال تشغيل يدوي

دعنا نبحث يدويًا عن القيمة المستهدفة 9 في المصفوفة التالية:

[5, 3, 8, 9, 2]

القيمة المستهدفة هي:

Target = 9

الخطوة 1: التحقق من العنصر الأول

العنصر الأول هو 5.

Index 0 → Value 5

قارن 5 بالهدف 9:

5 == 9 ? No

لم يتم العثور على القيمة، لذا تنتقل الخوارزمية إلى العنصر التالي.

الخطوة 2: التحقق من العنصر الثاني

العنصر الثاني هو 3.

Index 1 → Value 3

قارن 3 بالهدف 9:

3 == 9 ? No

لم يتم العثور على القيمة بعد، لذا تستمر الخوارزمية.

الخطوة 3: التحقق من العنصر الثالث

العنصر الثالث هو 8.

Index 2 → Value 8

قارن 8 بالهدف 9:

8 == 9 ? No

تنتقل الخوارزمية إلى العنصر التالي.

الخطوة 4: التحقق من العنصر الرابع

العنصر الرابع هو 9.

Index 3 → Value 9

قارن 9 بالهدف 9:

9 == 9 ? Yes

تم العثور على القيمة المستهدفة في الفهرس 3.

نتيجة البحث

Target 9 found at index 3

تتوقف الخوارزمية بمجرد العثور على الهدف. لا تحتاج إلى التحقق من العنصر الأخير 2.

تشغيل يدوي عندما لا يتم العثور على القيمة

الآن دعنا نبحث عن القيمة المستهدفة 6 في نفس المصفوفة:

[5, 3, 8, 9, 2]

القيمة المستهدفة هي:

Target = 6

تتحقق الخوارزمية من كل عنصر:

Index 0 → 5 == 6 ? No
Index 1 → 3 == 6 ? No
Index 2 → 8 == 6 ? No
Index 3 → 9 == 6 ? No
Index 4 → 2 == 6 ? No

يصل البحث إلى نهاية المصفوفة دون العثور على الهدف.

نتيجة البحث

Target 6 was not found

هذا هو أسوأ سلوك ممكن للبحث الخطي لأن كل عنصر يجب التحقق منه.

خطوات خوارزمية البحث الخطي

يمكن وصف خوارزمية البحث الخطي باستخدام هذه الخطوات:

1. استقبل مصفوفة وقيمة مستهدفة.

2. ابدأ من الفهرس الأول للمصفوفة.

3. قارن القيمة الحالية بالهدف.

4. إذا كانت القيمة الحالية تساوي الهدف، أعد الفهرس الحالي.

5. إذا لم تكن كذلك، انتقل إلى العنصر التالي.

6. كرر حتى يتم العثور على الهدف أو تنتهي المصفوفة.

7. إذا انتهت المصفوفة بدون تطابق، أعد -1 أو نتيجة "غير موجود".

هذا الهيكل بسيط ويعمل مع أي مجموعة تشبه القائمة تقريبًا.

الشفرة الزائفة (Pseudocode)

linearSearch(array, target):
    for i from 0 to length(array) - 1:
        if array[i] == target:
            return i

    return -1

تعتمد القيمة المعادة على التنفيذ. تعيد العديد من الخوارزميات فهرس العنصر الذي تم العثور عليه. إذا لم يتم العثور على العنصر، فإنها تعيد -1.

مثال على البحث الخطي في PHP

إليك تطبيق PHP نظيف للبحث الخطي:

<?php

function linearSearch(array $items, mixed $target): int
{
    foreach ($items as $index => $item) {
        if ($item === $target) {
            return $index;
        }
    }

    return -1;
}

$numbers = [5, 3, 8, 9, 2];

$result = linearSearch($numbers, 9);

echo $result;

سيكون الناتج:

3

القيمة 9 موجودة في الفهرس 3، لذا تعيد الدالة 3.

البحث الخطي في PHP عندما لا يتم العثور على القيمة

إذا بحثنا عن قيمة غير موجودة:

<?php

$numbers = [5, 3, 8, 9, 2];

$result = linearSearch($numbers, 6);

echo $result;

سيكون الناتج:

-1

تعيد الدالة -1 لأن القيمة المستهدفة 6 غير موجودة في المصفوفة.

مثال على البحث الخطي في JavaScript

إليك نفس الخوارزمية مطبقة في JavaScript:

function linearSearch(items, target) {
    for (let i = 0; i < items.length; i++) {
        if (items[i] === target) {
            return i;
        }
    }

    return -1;
}

const numbers = [5, 3, 8, 9, 2];

console.log(linearSearch(numbers, 9));

سيكون الناتج:

3

تتبع نسخة JavaScript نفس منطق نسخة PHP. تقوم بالتكرار عبر المصفوفة وتعيد الفهرس عند العثور على الهدف.

البحث الخطي مع السلاسل النصية (Strings)

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

على سبيل المثال، يمكننا البحث عن اسم داخل مصفوفة:

<?php

$names = ['Ali', 'Sara', 'Omar', 'Lina'];

$result = linearSearch($names, 'Omar');

echo $result;

سيكون الناتج:

2

الاسم عمر موجود في الفهرس 2.

البحث الخطي مع الكائنات (Objects)

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

إليك مثال PHP يبحث عن مستخدم بواسطة المعرف:

<?php

function findUserById(array $users, int $targetId): ?array
{
    foreach ($users as $user) {
        if ($user['id'] === $targetId) {
            return $user;
        }
    }

    return null;
}

$users = [
    ['id' => 1, 'name' => 'Ali'],
    ['id' => 2, 'name' => 'Sara'],
    ['id' => 3, 'name' => 'Omar'],
];

$user = findUserById($users, 2);

print_r($user);

سيكون الناتج:

Array
(
    [id] => 2
    [name] => Sara
)

هذا المثال أقرب إلى تطوير الواجهة الخلفية (backend) الحقيقي لأن البحث بواسطة المعرف عملية شائعة.

البحث الخطي مع الكائنات في JavaScript

إليك مثال مشابه في JavaScript:

function findUserById(users, targetId) {
    for (const user of users) {
        if (user.id === targetId) {
            return user;
        }
    }

    return null;
}

const users = [
    { id: 1, name: 'Ali' },
    { id: 2, name: 'Sara' },
    { id: 3, name: 'Omar' }
];

console.log(findUserById(users, 2));

سيكون الناتج:

{ id: 2, name: 'Sara' }

هذا لا يزال بحثًا خطيًا لأن الخوارزمية تتحقق من المستخدمين واحدًا تلو الآخر حتى تجد معرفًا مطابقًا.

التعقيد الزمني للبحث الخطي

يصف التعقيد الزمني كيف يزداد وقت تشغيل الخوارزمية مع زيادة حجم الإدخال. يتميز البحث الخطي بتعقيد زمني بسيط لأنه يتحقق من العناصر واحدًا تلو الآخر.

يحتوي البحث الخطي على ثلاث حالات مهمة للتعقيد الزمني:

• أفضل حالة: O(1)

• الحالة المتوسطة: O(n)

• أسوأ حالة: O(n)

حيث n هو عدد العناصر في المصفوفة.

أفضل حالة للتعقيد الزمني: O(1)

تحدث أفضل حالة عندما يتم العثور على القيمة المستهدفة في الموضع الأول.

Array:  [9, 5, 3, 8, 2]
Target: 9

تتحقق الخوارزمية من العنصر الأول:

9 == 9 ? Yes

تم العثور على القيمة على الفور، لذا تقوم الخوارزمية بإجراء مقارنة واحدة فقط.

لذلك، أفضل حالة للتعقيد الزمني هي:

O(1)

هذا يعني وقتًا ثابتًا. يتم العثور على النتيجة فورًا بغض النظر عن حجم المصفوفة.

الحالة المتوسطة للتعقيد الزمني: O(n)

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

Array:  [5, 3, 8, 9, 2]
Target: 8

قد تحتاج الخوارزمية إلى التحقق من عدة عناصر قبل العثور على الهدف.

في المتوسط، يتحقق البحث الخطي من حوالي نصف المصفوفة. ومع ذلك، في تدوين Big O، يتم تجاهل الثوابت، لذا فإن نصف n لا يزال يُكتب على النحو التالي:

O(n)

هذا يعني أن وقت التشغيل ينمو خطيًا مع نمو حجم الإدخال.

أسوأ حالة للتعقيد الزمني: O(n)

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

Array:  [5, 3, 8, 9, 2]
Target: 2

تتحقق الخوارزمية من كل عنصر حتى تصل إلى الأخير.

5 == 2 ? No
3 == 2 ? No
8 == 2 ? No
9 == 2 ? No
2 == 2 ? Yes

إذا لم يكن الهدف موجودًا، فإن الخوارزمية لا تزال تتحقق من كل عنصر قبل إرجاع "غير موجود".

لذلك، أسوأ حالة للتعقيد الزمني هي:

O(n)

لماذا البحث الخطي هو O(n)

البحث الخطي هو O(n) لأن عدد عمليات التحقق ينمو بشكل مباشر مع عدد العناصر.

إذا كانت المصفوفة تحتوي على 10 عناصر، فقد تتطلب أسوأ حالة 10 عمليات تحقق. إذا كانت المصفوفة تحتوي على 1000 عنصر، فقد تتطلب أسوأ حالة 1000 عملية تحقق. إذا كانت المصفوفة تحتوي على 1,000,000 عنصر، فقد تتطلب أسوأ حالة 1,000,000 عملية تحقق.

تسمى هذه العلاقة المباشرة بالنمو الخطي.

Input size: 10        Maximum checks: 10
Input size: 100       Maximum checks: 100
Input size: 1000      Maximum checks: 1000

لهذا السبب تُسمى الخوارزمية البحث الخطي ولماذا يكون تعقيدها الزمني في أسوأ حالة هو O(n).

التعقيد المكاني للبحث الخطي

يصف التعقيد المكاني مقدار الذاكرة الإضافية التي تستخدمها الخوارزمية. يحتاج البحث الخطي فقط إلى عدد قليل من المتغيرات مثل الفهرس والقيمة المستهدفة.

لا تنشئ مصفوفة أخرى أو بنية بيانات.

لذلك، التعقيد المكاني هو:

O(1)

هذا يعني أن البحث الخطي يستخدم ذاكرة إضافية ثابتة.

هل يتطلب البحث الخطي بيانات مرتبة؟

لا، لا يتطلب البحث الخطي بيانات مرتبة. هذه إحدى مزاياه الرئيسية.

يعمل البحث الخطي على:

• المصفوفات المرتبة.

• المصفوفات غير المرتبة.

• المصفوفات ذات القيم المكررة.

• مصفوفات الأرقام.

• مصفوفات السلاسل النصية.

• مصفوفات الكائنات أو السجلات.

نظرًا لأن البحث الخطي يتحقق من كل عنصر واحدًا تلو الآخر، فإنه لا يحتاج إلى أي ترتيب خاص.

البحث الخطي مع القيم المكررة

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

على سبيل المثال:

Array:  [4, 2, 7, 2, 9]
Target: 2

يظهر الهدف 2 في الفهرس 1 والفهرس 3. يعيد البحث الخطي القياسي الفهرس 1 لأنه أول تطابق.

Result: 1

إذا احتاج المطورون إلى جميع المواضع المتطابقة، فيجب أن تستمر الخوارزمية في البحث بعد العثور على أول تطابق.

العثور على جميع التطابقات باستخدام البحث الخطي

في بعض الأحيان لا نريد فقط التطابق الأول. قد نحتاج إلى جميع الفهارس التي يظهر فيها الهدف.

إليك مثال في PHP:

<?php

function findAllIndexes(array $items, mixed $target): array
{
    $indexes = [];

    foreach ($items as $index => $item) {
        if ($item === $target) {
            $indexes[] = $index;
        }
    }

    return $indexes;
}

$numbers = [4, 2, 7, 2, 9];

print_r(findAllIndexes($numbers, 2));

سيكون الناتج:

Array
(
    [0] => 1
    [1] => 3
)

هذا الإصدار لا يتوقف بعد التطابق الأول. إنه يفحص المصفوفة بأكملها ويجمع جميع الفهارس المتطابقة.

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

البحث الخطي والبحث الثنائي كلاهما خوارزميات بحث، لكنهما يعملان بشكل مختلف.

يتحقق البحث الخطي من العناصر واحدًا تلو الآخر. يقسم البحث الثنائي المصفوفة المرتبة إلى نصفين بشكل متكرر.

تشمل الاختلافات الرئيسية:

• يعمل البحث الخطي على البيانات غير المرتبة.

• يتطلب البحث الثنائي بيانات مرتبة.

• يحتوي البحث الخطي على تعقيد زمني في أسوأ حالة O(n).

• يحتوي البحث الثنائي على تعقيد زمني في أسوأ حالة O(log n).

• البحث الخطي أبسط في التنفيذ.

• البحث الثنائي أسرع للمصفوفات الكبيرة المرتبة.

إذا كانت البيانات صغيرة أو غير مرتبة، يمكن أن يكون البحث الخطي خيارًا جيدًا. أما إذا كانت البيانات كبيرة ومرتبة، فإن البحث الثنائي عادة ما يكون أسرع بكثير.

البحث الخطي مقابل البحث في جداول التجزئة (Hash Table)

البحث في جداول التجزئة (Hash Table lookup) يكون عادةً أسرع بكثير من البحث الخطي عند البحث بواسطة مفتاح. في العديد من لغات البرمجة، يمكن للمصفوفات الترابطية (associative arrays)، والخرائط (maps)، والقواميس (dictionaries)، أو الكائنات (objects) أن توفر وقت بحث متوسط يقارب O(1).

على سبيل المثال، يتطلب البحث عن مستخدم بواسطة المعرف في مصفوفة بسيطة التحقق من المستخدمين واحدًا تلو الآخر. ولكن إذا تم تخزين المستخدمين في خريطة (map) حيث يكون المعرف هو المفتاح، يمكن أن يكون البحث أسرع بكثير.

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

متى يجب على المطورين استخدام البحث الخطي؟

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

البحث الخطي مفيد عندما:

• مجموعة البيانات صغيرة.

• المصفوفة غير مرتبة.

• عملية البحث لا تتكرر كثيرًا.

• بنية البيانات لا تدعم البحث الأسرع.

• الكود يحتاج إلى أن يكون بسيطًا وقابلًا للقراءة.

• قد يتم العثور على الهدف بالقرب من البداية.

• يحتاج المطور إلى البحث في الكائنات باستخدام شروط مخصصة.

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

متى لا تستخدم البحث الخطي

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

يجب على المطورين تجنب البحث الخطي عندما:

• مجموعة البيانات كبيرة جدًا.

• تتكرر عمليات البحث عدة مرات.

• يمكن فرز البيانات واستخدام البحث الثنائي.

• يمكن فهرسة البيانات باستخدام جدول تجزئة أو فهرس قاعدة بيانات.

• الأداء حرج.

بالنسبة للأنظمة الكبيرة، عادة ما يكون من الأفضل استخدام الفهارس (indexes)، والخرائط (maps)، واستعلامات قواعد البيانات (database queries)، أو هياكل بيانات أكثر ملاءمة.

مثال عملي: البحث عن منتج بواسطة SKU

تخيل قائمة صغيرة من المنتجات حيث يمتلك كل منتج رمز SKU. إذا كانت القائمة صغيرة، يمكن للبحث الخطي العثور على المنتج بوضوح ومباشرة.

<?php

function findProductBySku(array $products, string $sku): ?array
{
    foreach ($products as $product) {
        if ($product['sku'] === $sku) {
            return $product;
        }
    }

    return null;
}

$products = [
    ['sku' => 'P100', 'name' => 'Keyboard'],
    ['sku' => 'P200', 'name' => 'Mouse'],
    ['sku' => 'P300', 'name' => 'Monitor'],
];

$product = findProductBySku($products, 'P200');

print_r($product);

سيكون الناتج:

Array
(
    [sku] => P200
    [name] => Mouse
)

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

مثال عملي: البحث عن عنصر قائمة

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

Menu items:
Home, About, Blog, Contact

Target:
Blog

تتحقق الخوارزمية من كل عنصر:

Home → not match
About → not match
Blog → match

لقائمة صغيرة، يعتبر البحث الخطي بسيطًا وفعالًا بما فيه الكفاية.

الأخطاء الشائعة عند تنفيذ البحث الخطي

البحث الخطي بسيط، ولكن المبتدئين لا يزال بإمكانهم ارتكاب الأخطاء.

تشمل الأخطاء الشائعة ما يلي:

• نسيان إرجاع قيمة "غير موجود".

• العودة مبكرًا جدًا قبل التحقق من جميع العناصر.

• استخدام مقارنة فضفاضة (loose comparison) عندما تكون هناك حاجة لمقارنة صارمة (strict comparison).

• الخلط بين القيمة والفهرس.

• متابعة الحلقة بعد العثور على الهدف بالفعل عندما يكون هناك حاجة لتطابق واحد فقط.

• استخدام البحث الخطي بشكل متكرر على بيانات كبيرة دون النظر في هياكل أفضل.

في PHP، غالبًا ما يكون استخدام المقارنة الصارمة === أكثر أمانًا من المقارنة الفضفاضة == لأنها تتحقق من القيمة والنوع معًا.

قائمة مراجعة عملية لفهم البحث الخطي

قبل الانتقال إلى البحث الثنائي (Binary Search) أو هياكل البيانات المتقدمة، يجب أن يكون المطورون قادرين على الإجابة على هذه الأسئلة:

• ماذا يفعل البحث الخطي؟

• هل يتطلب البحث الخطي بيانات مرتبة؟

• ماذا يحدث عندما يتم العثور على الهدف في العنصر الأول؟

• ماذا يحدث عندما لا يتم العثور على الهدف؟

• لماذا أفضل حالة هي O(1)؟

• لماذا أسوأ حالة هي O(n)؟

• ما هو التعقيد المكاني؟

• متى يجب استبدال البحث الخطي بالبحث الثنائي أو جدول التجزئة؟

إذا كانت هذه الأسئلة واضحة، فإن المطور يفهم المنطق الحقيقي للبحث الخطي، وليس فقط الكود.

مزايا البحث الخطي

يتمتع البحث الخطي بالعديد من المزايا التي تجعله مفيدًا في مواقف محددة.

• من السهل جدًا فهمه.

• من السهل تنفيذه.

• يعمل على البيانات غير المرتبة.

• يعمل مع الأرقام والسلاسل النصية والكائنات.

• لا يتطلب ذاكرة إضافية.

• يمكنه التوقف مبكرًا عند العثور على الهدف.

• مفيد لمجموعات البيانات الصغيرة.

هذه المزايا تجعل البحث الخطي خوارزمية بحث أولى جيدة للمبتدئين.

عيوب البحث الخطي

للبحث الخطي أيضًا قيود مهمة.

• إنه بطيء لمجموعات البيانات الكبيرة.

• تعقيده الزمني في الحالة المتوسطة والأسوأ هو O(n).

• لا يستفيد من البيانات المرتبة.

• يمكن أن يصبح غير فعال عند تكراره عدة مرات.

• عادة ما يكون أسوأ من البحث المفهرس للمجموعات الكبيرة.

بسبب هذه القيود، ليس البحث الخطي هو الخيار الأفضل للبحث الحرج من حيث الأداء في الأنظمة الكبيرة.

البحث الخطي في مشاريع البرمجيات الحقيقية

يظهر البحث الخطي في مشاريع البرمجيات الحقيقية أكثر مما يتوقع العديد من المبتدئين. يستخدمه المطورون عند تصفية المصفوفات، العثور على سجلات في مجموعات صغيرة، التحقق من الخيارات المختارة، التحقق من صحة قيمة مقابل قائمة قصيرة، أو البحث في الكائنات حسب شرط معين.

على سبيل المثال، قد يتلقى تطبيق Laravel أو PHP مصفوفة صغيرة من الإعدادات أو الأدوار أو العلامات أو الحقول المختارة. يمكن أن يكون البحث عبر هذه المصفوفة الصغيرة باستخدام حلقة بسيطة أوضح من بناء بنية بيانات معقدة.

ومع ذلك، عند البحث في سجلات قاعدة البيانات، يجب على المطورين عادةً الاعتماد على استعلامات قواعد البيانات والفهارس بدلاً من تحميل كميات كبيرة من البيانات في الذاكرة والبحث باستخدام البحث الخطي يدويًا.

الخاتمة

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

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

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

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