Pencarian linear

Pencarian linear adalah cara mencari yang paling sederhana: periksa setiap data mulai dari yang pertama. Jika ketemu, kembalikan posisinya. Jika sampai akhir tidak ketemu, kembalikan tanda "tidak ada", biasanya -1.

1def cari_linear(data, target):2    for i in range(len(data)):3        if data[i] == target:4            return i5    return -167nilai = [72, 85, 64, 91, 78, 55]8print(cari_linear(nilai, 91))9print(cari_linear(nilai, 100))

3
-1

Berapa banyak perbandingan?

Kecepatan algoritma pencarian diukur dari banyaknya perbandingan yang dilakukan.

1def cari_linear_hitung(data, target):2    banding = 03    for i in range(len(data)):4        banding += 15        if data[i] == target:6            return i, banding7    return -1, banding89data = list(range(1, 1001))10print(cari_linear_hitung(data, 1))11print(cari_linear_hitung(data, 500))12print(cari_linear_hitung(data, 1000))13print(cari_linear_hitung(data, 5000))

(0, 1)
(499, 500)
(999, 1000)
(-1, 1000)

Banyaknya perbandingan tumbuh sebanding dengan banyaknya data. Data dua kali lebih banyak berarti pencarian terburuknya dua kali lebih lama.

Kelebihan pencarian linear

• Bisa dipakai untuk data yang tidak urut.
• Mudah ditulis dan sulit salah.
• Cukup cepat untuk data kecil.

Operator in dan metode index() pada list Python sebenarnya melakukan pencarian linear.

1def cari_semua(data, target):2    posisi = []3    for i, nilai in enumerate(data):4        if nilai == target:5            posisi.append(i)6    return posisi78print(cari_semua([5, 3, 5, 8, 5, 1], 5))9print(cari_semua([5, 3, 5, 8, 5, 1], 7))

[0, 2, 4]
[]