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

Question

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

IT Interview Practice · 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) كافٍ تمنع التحسين المبكر.

الفكرة

مثال

التعقيد

متى تستخدمه

لماذا هذا مهم

أسئلة ذات صلة