რა არის წრფივი ძიება?

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
```

## სირთულე

- **დრო:** O(n) ყველაზე ცუდი შემთხვევა (მიზანი ბოლოს ან არ არსებობს), O(1) საუკეთესო შემთხვევა.
- **სივრცე:** O(1).

## როდის უნდა გამოიყენოთ

- მონაცემები **არადალაგებულია** და თქვენ არ შეგიძლიათ მათი დალაგება.
- სია მცირე, ამიტომ O(n) უმნიშვნელოა.
- თქვენ გჭირდებათ ერთჯერადი ძიება, სადაც ინდექსის შექმნა ან წინასწარი დალაგება ღირებული არ არის.

თუ ხშირად ძებნით, დაასახელეთ დალაგებული მასივი binary search-ით ან hash set O(1) საშუალო ძიებებისთვის.

## რატომ არის ეს მნიშვნელოვანი

წრფივი ძიება არის საბაზო ხაზი, რომელიც ყველა სხვა ძიების ფარგლებში იზომება.

ეს გახსენებთ, რომ *სწორი* ალგორითმი დამოკიდებულია მონაცემებზე: არადალაგებული და ძალიან პატარა ამჯობინებს მარტივ სკანირებას; დიდი და განმეორებით ნაკრებული ამჯობინებს უფრო ჭკვიან სტრუქტურებს.

თუ იცით, როდის არის O(n) საკმარისი, ეს ხელს შეუშლის ზედმეტი ოპტიმიზაციას.