linear search とは何ですか？

Question

Accepted Answer

**Linear search** は collection を element by element に scan し、target を見つけるか end に達するまで進みます。sorted かどうかに関係なく **any** list で動きますが、time は **O(n)** です。

## 考え方

order に関する assumption はありません。各 item を 1 つずつ確認します。

## 例

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # left to right に進む
        if value == target:
            return i                  # found した index を返す
    return -1                         # full scan 後も not found

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

## Complexity

- **Time:** worst case O(n)（target が最後または absent）、best case O(1)。
- **Space:** O(1)。

## いつ使うか

- data が **unsorted** で、sort する余裕がない。
- list が小さく O(n) が問題にならない。
- one-off lookup で index や sort を作る価値がない。

repeated search なら、sorted array + binary search、または average O(1) lookup の hash set を検討します。

## なぜ重要なのか

linear search は他の search algorithm の baseline です。right algorithm は data に依存することを教えてくれます。unsorted and tiny なら simple scan、大きく繰り返し query するなら smarter structure が向きます。O(n) で十分な場面を知ることは premature optimization を防ぎます。