Apakah linear search?

Question

Accepted Answer

**Linear search** mengimbas koleksi elemen demi elemen sehingga ia menemukan target atau sampai ke akhir. Ia berfungsi pada **sebarang** senarai — disusun atau tidak — tetapi berjalan dalam masa **O(n)**.

## Ideanya

Tiada andaian tentang perintah: hanya semak setiap item satu demi 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
```

## Kerumitan

- **Masa:** O(n) kes terburuk (sasaran akhir atau tiada), O(1) kes terbaik.
- **Ruang:** O(1).

## Bila hendak digunakan

- Data adalah **tidak disusun** dan anda tidak mampu menyusunnya.
- Senarai kecil, jadi O(n) dapat diabaikan.
- Anda perlukan pencarian sekali kali di mana membina indeks atau menyusun terlebih dahulu tidak berbaloi.

Jika anda mencari berulang kali, lebih suka tatasusunan tersusun dengan binary search atau set hash untuk purata carian O(1).

## Mengapa ia penting

Linear search ialah garis asas yang mana semua pencarian lain diukur.

Ia mengingatkan anda bahawa algoritma *tepat* bergantung pada data: tidak disusun dan kecil memihak imbasan mudah; besar dan ditanya berulang kali memihak struktur yang lebih bijak.

Mengetahui bila O(n) cukup baik menghalang pengoptimuman pramatang.