Apa itu pencarian linear?

Question

Accepted Answer

**Linear search** memindai koleksi elemen demi elemen sampai menemukan target atau mencapai akhir. Berfungsi pada **daftar apa pun** — terurut atau tidak — tetapi berjalan dalam waktu **O(n)**.

## Idenya

Tanpa asumsi tentang urutan: cukup periksa setiap item satu per satu.

## Contoh

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

## Kompleksitas

- **Waktu:** O(n) kasus terburuk (target terakhir atau hilang), O(1) kasus terbaik.
- **Ruang:** O(1).

## Kapan menggunakannya

- Data **tidak terurut** dan Anda tidak dapat mengurutkannya.
- Daftarnya kecil, jadi O(n) dapat diabaikan.
- Anda memerlukan pencarian sekali kali di mana membangun indeks atau mengurutkan terlebih dahulu tidak sepadan.

Jika Anda mencari berulang kali, lebih suka larik terurut dengan pencarian biner atau hash set untuk pencarian rata-rata O(1).

## Mengapa ini penting

Pencarian linear adalah baseline yang diukur semua pencarian lainnya.

Ini mengingatkan Anda bahwa algoritma *yang tepat* tergantung pada data: tidak terurut dan kecil mendukung pemindaian sederhana; besar dan sering dipertanyakan mendukung struktur yang lebih cerdas.

Mengetahui kapan O(n) cukup mencegah optimasi prematur.