Pencarian Linear di Python: Panduan Pemula dengan Contoh

Saat membahas algoritma pencarian, pencarian linear adalah salah satu yang paling sederhana. Jika Anda pernah menelusuri daftar item satu per satu hingga menemukan apa yang Anda cari, maka Anda sudah melakukan pencarian linear!

Selain mudah dipahami, pencarian linear berguna karena dapat bekerja pada data yang tidak terurut, berbeda dengan beberapa algoritma pencarian lainnya. Fleksibilitas ini menjadikannya opsi yang bermanfaat dalam skenario ketika pengurutan data tidak memungkinkan. Saya akan menggunakan Python dalam tutorial ini, jadi jika sebelum mulai Anda ingin menyegarkan ingatan tentang Python, lihat jalur keterampilan Python Programming.

Apa itu Pencarian Linear?

Pencarian linear adalah algoritma yang menemukan nilai tertentu dalam sebuah daftar dengan memeriksa setiap elemen satu per satu. Algoritma dimulai dari item pertama, membandingkannya dengan target, lalu terus bergerak melalui daftar hingga menemukan target atau mencapai akhir daftar. Ini adalah algoritma yang sederhana dan intuitif.

Pencarian linear tidak memerlukan data diurutkan agar dapat bekerja, sehingga utamanya digunakan pada dataset yang tidak terurut. Hal ini membuatnya praktis untuk situasi ketika pengurutan tidak memungkinkan, atau Anda bekerja dengan data mentah. Namun, keunggulan ini ada harganya: pencarian linear tidak seefisien algoritma lain yang memerlukan data sudah diurutkan.

Pencarian linear ideal untuk situasi ketika Anda bekerja dengan dataset yang relatif kecil atau ketika pengurutan data tidak layak. Diagram di bawah ini memberikan penjelasan yang disederhanakan.

Memilih Pencarian Linear

Mari kita lihat keunggulan-keunggulannya dan juga satu kelemahan yang menonjol: 

Mengapa Memilih Pencarian Linear?

Menurut saya, pencarian linear memiliki tiga manfaat utama:

Ketika Kesederhanaan yang Utama

Salah satu keunggulan terbesar pencarian linear adalah kesederhanaannya. Algoritmanya mudah dipahami dan diimplementasikan. Tidak perlu repot dengan pengurutan kompleks atau membagi data. Cukup mulai dari awal daftar dan periksa setiap elemen hingga Anda menemukan apa yang dicari.

Ketika Anda Tidak Punya Waktu untuk Mengurutkan

Berbeda dengan algoritma pencarian lain seperti pencarian biner, pencarian linear tidak mengharuskan dataset diurutkan. Ini menjadikannya sempurna ketika Anda membutuhkan cara cepat untuk menemukan sesuatu.

Ketika Anda Membutuhkan Versatilitas

Keunggulan lain dari pencarian linear adalah sifatnya yang serbaguna. Algoritma ini bekerja tidak hanya dengan array tetapi juga dengan struktur data Python lainnya, seperti linked list. Selama Anda dapat mengakses elemen secara berurutan, pencarian linear bisa menyelesaikan tugas. Algoritma ini cukup fleksibel untuk menangani berbagai jenis data, dari angka hingga string, bahkan objek.

Mengapa Perlu Berpikir Dua Kali tentang Pencarian Linear?

Ada satu hal yang perlu dipertimbangkan:

Ketika Efisiensi Penting

Kelemahan utama pencarian linear adalah ketidakefisienannya, terutama pada dataset besar. Kompleksitas waktunya O(n), yang berarti dalam kasus terburuk Anda mungkin harus memeriksa setiap elemen dalam daftar! Ini dapat sangat memperlambat proses jika Anda bekerja dengan ribuan atau jutaan entri. Namun, untuk dataset kecil, ketidakefisienan ini mungkin dapat diabaikan.

Mengimplementasikan Algoritma Pencarian Linear di Python

Di Python, ada dua cara umum untuk menulis pencarian linear: metode iteratif dan metode rekursif. Untuk mendemonstrasikan kedua metode ini, mari terlebih dahulu membuat dataset sederhana berisi 100 angka tanpa duplikasi.

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]Didukung oleh

Metode iteratif

Pendekatan iteratif mungkin cara termudah untuk memahami pencarian linear. Anda melakukan loop melalui daftar, memeriksa setiap elemen hingga menemukan target atau mencapai akhir.

Pertama, kita akan membuat fungsinya:

1. Kita akan melakukan loop melalui setiap elemen dalam daftar arr.

2. Kita akan membandingkan setiap elemen dengan target.

3. Jika ditemukan kecocokan, kita mengembalikan indeks tempat target ditemukan.

4. Jika kita menyelesaikan loop tanpa menemukan target, kita mengembalikan 1 untuk menunjukkan bahwa elemen tidak ada.

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not foundDidukung oleh

Selanjutnya, kita akan menjalankan fungsi pada dataset kita, dan mencetak hasilnya:

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")Didukung oleh

Menjalankan kode ini, kita menemukan nilai target pada elemen ke-23.

Metode rekursif

Metode rekursif menggunakan fungsi yang memanggil dirinya sendiri untuk melakukan pencarian dalam daftar. Setiap panggilan rekursif memproses satu elemen pada satu waktu dan kemudian berlanjut ke elemen berikutnya. Proses ini berlanjut hingga target ditemukan atau akhir daftar tercapai.

Mari kita buat fungsi rekursifnya:

1. Kita akan mulai dengan memeriksa elemen pertama (pada indeks 0).
2. Jika target cocok, kita akan mengembalikan indeksnya.
3. Jika target tidak cocok, kita akan memanggil fungsi yang sama secara rekursif, tetapi menambahkan indeks sebesar 1 untuk memeriksa elemen berikutnya.
4. Rekursi berlanjut hingga kita menemukan target atau mencapai akhir daftar.

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next elementDidukung oleh

Kita dapat menggunakan kode yang sama seperti di atas untuk menjalankan fungsi ini dan fungsi tersebut mengembalikan nilai indeks yang sama untuk target kita: 23.

Perlu diingat bahwa pendekatan ini menggunakan lebih banyak memori karena setiap pemanggilan rekursif menambahkan lapisan baru ke call stack. Lihat Understanding Recursive Functions in Python untuk meninjau rekursi lebih dekat.

Kompleksitas Waktu dan Ruang

Salah satu cara untuk mengevaluasi efisiensi algoritma adalah dengan melihat kompleksitas waktu dan ruangnya. Lihat tutorial Analyzing Complexity of Code through Python untuk melihat berbagai cara mengukur kompleksitas algoritma.

Kompleksitas waktu

Kompleksitas waktu suatu algoritma merujuk pada bagaimana waktu yang dibutuhkan untuk menyelesaikan meningkat seiring bertambahnya ukuran masukan. Kompleksitas waktu pencarian linear adalah O(n), di mana n adalah jumlah elemen dalam daftar. Artinya, dalam kasus terburuk, algoritma mungkin perlu memeriksa setiap elemen sebelum menemukan target (atau menentukan bahwa target tidak ada dalam daftar). Ini cukup tidak efisien, terutama untuk dataset besar. Itulah mengapa pencarian linear paling baik digunakan ketika kita memiliki dataset kecil yang tidak terurut dan hanya perlu ditelusuri sekali.

Kompleksitas ruang

Kompleksitas ruang suatu algoritma mengukur seberapa banyak memori yang dibutuhkan seiring bertambahnya ukuran masukan. Kompleksitas ruang algoritma pencarian linear bergantung pada metode yang kita gunakan. Untuk metode iteratif, kompleksitas ruang adalah O(1), yang berarti algoritma membutuhkan jumlah memori konstan, terlepas dari ukuran daftar masukan. Ini karena versi iteratif tidak memerlukan memori tambahan, selain daftar masukan dan beberapa variabel untuk melacak indeks saat ini.

Untuk metode rekursif, kompleksitas ruang adalah O(n), yang berarti kebutuhan memori bertambah secara linear dengan ukuran daftar masukan. Ini disebabkan oleh pemanggilan fungsi rekursif, yang menambahkan lapisan pada call stack untuk setiap elemen dalam daftar. Daftar yang lebih besar membutuhkan lebih banyak memori untuk menyimpan pemanggilan tersebut, membuat pendekatan rekursif kurang efisien dari sisi ruang.

Aplikasi Dunia Nyata dari Pencarian Linear

Meskipun pencarian linear bukanlah algoritma paling efisien untuk dataset besar, algoritma ini memiliki kegunaan praktis dalam banyak skenario. Mari kita lihat beberapa situasi di mana pencarian linear adalah alat terbaik untuk pekerjaan tersebut.

Dataset kecil di mana pengurutan tidak praktis

Pencarian linear sering menjadi pilihan utama saya saat menangani dataset kecil yang tidak sepadan untuk diurutkan dari sisi waktu atau sumber daya. Dalam kasus seperti ini, kesederhanaan pencarian linear bisa lebih efisien dibanding overhead mengurutkan data untuk algoritma pencarian yang lebih kompleks.

Menemukan kemunculan pertama dari sebuah target

Kasus penggunaan umum lainnya untuk pencarian linear adalah ketika Anda perlu menemukan kemunculan pertama dari nilai target. Karena pencarian linear bergerak melalui daftar satu elemen pada satu waktu, algoritma ini secara alami menemukan kemunculan pertama dari target dan mengembalikan posisinya. Ini sangat berguna, misalnya saat menelusuri sebuah string untuk kemunculan pertama suatu karakter.

Ketika penyiapan minimal diperlukan

Terkadang, kesederhanaan pencarian linear menjadikannya opsi terbaik. Misalnya, jika Anda dengan cepat menelusuri data yang tidak Anda rencanakan untuk digunakan kembali atau Anda memerlukan jawaban kasar dengan cepat, penyiapan minimal dari pencarian linear dapat menghemat waktu.

Pencarian Linear vs. Algoritma Pencarian Lainnya

Pencarian linear hanyalah salah satu dari banyak algoritma pencarian yang ada. Mari kita lihat dua algoritma pencarian umum lainnya: pencarian biner dan hash lookup.

Pencarian linear vs. pencarian biner

Pencarian biner adalah algoritma yang menemukan posisi nilai target dalam array yang sudah diurutkan dengan berulang kali membagi interval pencarian menjadi dua. Kompleksitas waktunya O(log n), membuatnya jauh lebih efisien dibanding pencarian linear. Namun, algoritma ini hanya bekerja pada data yang sudah diurutkan. Ketika dataset Anda sudah diurutkan, pencarian biner hampir selalu menjadi pilihan yang lebih baik karena memangkas ruang pencarian setengahnya di setiap langkah, secara drastis mengurangi jumlah perbandingan yang diperlukan untuk menemukan target.

Pencarian linear bisa lebih tepat digunakan dalam situasi ketika data Anda tidak terurut, karena pencarian linear bekerja pada dataset apa pun, baik terurut maupun tidak. Namun, dengan kompleksitas waktu O(n), pencarian linear jauh lebih tidak efisien pada dataset yang sudah diurutkan.

Pencarian linear vs. hash lookup

Hash lookup adalah metode yang menggunakan tabel hash untuk dengan cepat menemukan sebuah elemen. Dengan kompleksitas waktu O(1), metode ini secara signifikan lebih cepat dibanding pencarian linear maupun biner. Namun, kecepatan ini ada biayanya: Anda perlu terlebih dahulu membangun tabel hash, yang memerlukan waktu dan memori tambahan. Hash lookup paling cocok ketika Anda perlu menelusuri dataset besar berkali-kali sehingga penyiapan awalnya terbayar seiring waktu.

Sebaliknya, pencarian linear tidak memerlukan penyiapan, menjadikannya opsi yang lebih lugas. Ini adalah pilihan yang lebih baik ketika Anda hanya perlu melakukan pencarian sekali atau beberapa kali saja, di mana waktu ekstra untuk menyiapkan tabel hash tidak dapat dibenarkan. Pencarian linear juga bisa lebih efisien dari sisi ruang karena Anda tidak perlu menyimpan tabel hash untuk menggunakan algoritma tersebut.

Jebakan Umum dan Cara Menghindarinya

Walau pencarian linear adalah algoritma yang lugas, ada beberapa kesalahan umum yang perlu diwaspadai.

Kesalahan off-by-one dalam iterasi

Salah satu kesalahan paling sering saat mengimplementasikan pencarian linear adalah kesalahan off-by-one. Ini terjadi karena memulai atau menghentikan iterasi pada indeks yang salah. Penting untuk diingat bahwa daftar Python menggunakan indeks mulai dari nol, artinya elemen pertama memiliki indeks 0. Melupakan hal ini dapat membuat Anda tanpa sengaja melewatkan elemen pertama atau beriterasi satu langkah terlalu jauh, yang mengarah pada hasil salah atau error.

Salah memahami indeks yang dikembalikan

Jebakan umum lainnya adalah salah memahami apa yang dikembalikan fungsi ketika target tidak ditemukan dalam daftar. Secara konvensi, banyak algoritma pencarian (termasuk pencarian linear) mengembalikan -1 untuk menunjukkan bahwa target tidak ada. Namun, beberapa pemula mungkin berasumsi fungsi mengembalikan None, False, atau nilai lain, sehingga menimbulkan kebingungan saat menafsirkan hasil.

Kapan tidak menggunakan pencarian linear

Seperti yang telah disebutkan, pencarian linear dengan cepat menjadi tidak efisien untuk dataset yang lebih besar. Karena itu, algoritma ini sebaiknya digunakan untuk dataset kecil yang tidak terurut atau pencarian cepat yang dilakukan sekali saja.

Kesimpulan

Sebagai salah satu metode pencarian paling sederhana, pencarian linear memeriksa setiap elemen dalam daftar secara berurutan, sehingga mudah dipahami dan diimplementasikan. Pencarian linear adalah pilihan andal untuk pencarian cepat yang dilakukan sekali pada dataset kecil, khususnya ketika data tidak terurut.

Jika Anda tertarik pada algoritma pencarian, lihat artikel lain dalam seri ini: Binary Search in Python, Depth-First Search in Python, dan Breadth-First Search in Python. Anda juga mungkin tertarik pada AVL Tree: Complete Guide With Python Implementation dan Introduction to Network Analysis in Python sebagai topik lanjutan.