লিনিয়ার সার্চ কি?

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) নগণ্য।
- আপনার একটি একমুখী লুকআপ প্রয়োজন যেখানে একটি index তৈরি করা বা আগে সাজানো মূল্যবান নয়।

যদি আপনি বারবার অনুসন্ধান করেন, তাহলে binary search সহ একটি সাজানো array বা O(1) গড় লুকআপের জন্য একটি hash set পছন্দ করুন।

## এটি কেন গুরুত্বপূর্ণ

লিনিয়ার সার্চ হল বেসলাইন যার বিপরীতে অন্য প্রতিটি সার্চ পরিমাপ করা হয়।

এটি আপনাকে মনে করিয়ে দেয় যে *সঠিক* অ্যালগরিদম ডেটার উপর নির্ভর করে: অসাজানো এবং ছোট সরল স্ক্যানকে অনুকূল করে; বড় এবং বারবার জিজ্ঞাসা করা হয় স্মার্টার কাঠামো অনুকূল করে।

কখন O(n) যথেষ্ট তা জানা অকাল অপ্টিমাইজেশন প্রতিরোধ করে।