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

Question

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

Accepted Answer

**البحث الخطي** يفحص مجموعة من العناصر واحداً تلو الآخر حتى يجد الهدف أو يصل إلى النهاية. يعمل على **أي** قائمة — مرتبة أم لا — لكنه يعمل في وقت **O(n)**.

## الفكرة

لا توجد افتراضات حول الترتيب: فقط تحقق من كل عنصر واحداً تلو الآخر.

## مثال

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # walk left to right
        if value == target:
            return i                  # return the index when found
    return -1                         # not found after full scan

linear_search([4, 2, 7, 1], 7)        # -> 2
```

## التعقيد

- **الوقت:** O(n) في أسوأ الحالات (الهدف في النهاية أو غير موجود)، O(1) في أفضل الحالات.
- **المساحة:** O(1).

## متى تستخدمه

- البيانات **غير مرتبة** ولا تستطيع تحمل تكلفة ترتيبها.
- القائمة صغيرة، لذا O(n) لا يذكر.
- تحتاج بحثاً لمرة واحدة حيث لا يستحق بناء فهرس أو الفرز أولاً.

إذا كنت تبحث بشكل متكرر، فضّل مصفوفة مرتبة مع البحث الثنائي أو مجموعة hash للبحث بمتوسط O(1).

## لماذا هذا مهم

البحث الخطي هو الخط الأساسي الذي يتم قياس جميع عمليات البحث الأخرى ضده.

إنه يذكرك بأن *الخوارزمية الصحيحة* تعتمد على البيانات: البيانات غير المرتبة والصغيرة تفضل المسح البسيط؛ البيانات الكبيرة والمستعلم عنها بشكل متكرر تفضل هياكل أذكى.

معرفة متى O(n) كافٍ تمنع التحسين المبكر.