Linear Search (Pencarian Linear)
Terakhir diperbarui
Linear search (disebut juga sequential search) adalah algoritma pencarian paling sederhana: mulai dari elemen pertama dan bandingkan setiap elemen dengan target sampai kamu menemukan yang cocok atau elemennya habis. Algoritma ini tidak membuat asumsi apa pun tentang datanya, jadi array boleh tidak terurut, dan elemennya boleh berupa apa saja yang bisa dibandingkan kesamaannya.
Animasi di atas menyorot setiap perbandingan saat pemindaian bergerak dari kiri ke kanan dan berhenti begitu target muncul. Kesederhanaannya dibayar dengan kecepatan: pada kasus terburuk, setiap elemen diperiksa, jadi algoritma ini berjalan dalam O(n). Jika datanya terurut, binary search menemukan jawaban yang sama dalam O(log n), dan jika kamu perlu mengurutkan data terlebih dahulu, lihat merge sort.
Kompleksitas waktu dan ruang
| Kasus | Kompleksitas | Catatan |
|---|---|---|
| Kasus terbaik | O(1) | Elemen pertama adalah target. |
| Kasus rata-rata | O(n) | Rata-rata separuh elemen diperiksa sebelum target ditemukan. |
| Kasus terburuk | O(n) | Target ada di posisi terakhir, atau sama sekali tidak ada. |
| Ruang | O(1) | Hanya indeks saat ini yang disimpan. |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Mulai dari indeks 0, elemen pertama array. |
| 2 | Bandingkan elemen saat ini dengan nilai target. |
| 3 | Jika sama, kembalikan indeks saat ini (ditemukan). |
| 4 | Jika tidak, geser satu posisi ke kanan dan ulangi. |
| 5 | Jika akhir array tercapai tanpa ada yang cocok, target tidak ada (kembalikan -1). |
Contoh penerapan
Mencari 5 di [7, 3, 9, 1, 5, 8, 2]:
| Perbandingan | Indeks | Elemen | Hasil |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5: lanjutkan pemindaian. |
| 2 | 1 | 3 | 3 ≠ 5: lanjutkan pemindaian. |
| 3 | 2 | 9 | 9 ≠ 5: lanjutkan pemindaian. |
| 4 | 3 | 1 | 1 ≠ 5: lanjutkan pemindaian. |
| 5 | 4 | 5 | 5 = 5: ditemukan di indeks 4. |
Kapan memakai linear search
| Pakai saat | Hindari saat |
|---|---|
| Datanya tidak terurut atau terus berubah | Datanya terurut, sehingga binary search jauh lebih cepat secara eksponensial |
| Koleksinya kecil, jadi kesederhanaan lebih menguntungkan | Datanya besar dan dicari berulang kali |
| Kamu hanya punya akses berurutan (stream, linked list) | Kamu sanggup memakai indeks atau hash table untuk pencarian O(1) |
Kode Linear Search
Implementasi Linear Search yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C, Pseudocode. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Linear Search dalam Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))Kode Linear Search dalam JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Kode Linear Search dalam Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}Kode Linear Search dalam C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}Kode Linear Search dalam C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Kode Linear Search dalam Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)FAQ Linear Search
Berapa kompleksitas waktu linear search?
O(n) pada kasus rata-rata dan terburuk (pemindaian mungkin harus mengunjungi setiap elemen) dan O(1) pada kasus terbaik saat elemen pertama adalah target. Ruang tambahan yang dipakai O(1).Apakah linear search membutuhkan data yang terurut?
Tidak, dan itulah keunggulan utamanya. Linear search bekerja pada data yang sama sekali tidak terurut karena memeriksa kesamaan setiap elemen; urutan tidak pernah berpengaruh. Sebaliknya, binary search hanya bekerja pada array yang terurut.
Kapan linear search lebih baik daripada binary search?
O(n log n)), saat koleksinya sangat kecil, atau saat kamu hanya punya akses berurutan seperti stream atau linked list. Untuk pencarian berulang pada array terurut, binary search yang menang.Apakah linear search sama dengan sequential search?
Ya, kedua nama itu merujuk ke algoritma yang sama: pindai elemen secara berurutan sampai target ditemukan atau koleksinya habis.
Berapa banyak perbandingan yang dilakukan linear search secara rata-rata?
n/2 perbandingan; jika target tidak ada, tepat n. Pertumbuhan linear itulah alasan algoritma ini disebut linear search.Sumber terkait
Visualisasi lainnya
