لکیری تلاش (Linear Search) کیا ہے؟

Question

Accepted Answer

**Linear search** ایک مجموعہ کو عنصر کے بعد عنصر اسکین کرتا ہے جب تک وہ ہدف تک نہ پہنچ جائے یا آخر تک پہنچ جائے۔ یہ **کسی بھی** لسٹ پر کام کرتا ہے — ترتیب شدہ ہو یا نہیں — لیکن **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
```

## Complexity

- **Time:** O(n) بدترین صورت (ہدف آخر میں یا موجود نہیں)، O(1) بہترین صورت۔
- **Space:** O(1)۔

## کب استعمال کریں

- ڈیٹا **غیر ترتیب شدہ** ہے اور آپ اسے ترتیب دینے کا خرچ نہیں اٹھا سکتے۔
- لسٹ چھوٹی ہے، تو O(n) نگہہاری کے قابل ہے۔
- آپ کو ایک بار کی تلاش کی ضرورت ہے جہاں index بنانا یا پہلے ترتیب دینا قابلِ قدر نہیں۔

اگر آپ بار بار تلاش کرتے ہیں، تو ترتیب شدہ array کو binary search کے ساتھ یا hash set کو O(1) اوسط تلاش کے لیے ترجیح دیں۔

## یہ کیوں اہم ہے

Linear search وہ بنیاد ہے جس کے خلاف ہر دوسری تلاش کا موازنہ کیا جاتا ہے۔

یہ آپ کو یاد دلاتا ہے کہ *صحیح* algorithm ڈیٹا پر منحصر ہے: غیر ترتیب شدہ اور چھوٹے لیے سادہ اسکین موزوں ہے؛ بڑے اور بار بار پوچھے جانے والے کے لیے ذہین ڈھانچے موزوں ہیں۔

یہ جاننا کہ O(n) کب کافی ہے بہت جلدی optimization سے بچاتا ہے۔