Pencarian Linier: Python, C++ Example
Sarah Chen
Apa itu Algoritma Pencarian?
Algoritma pencarian dirancang untuk menemukan elemen atau objek dari kumpulan elemen atau objek dengan struktur data tertentu. Misalnya, mencari tinggi minimum dari daftar tinggi yang diberikan, atau mencari nilai tertinggi dari daftar atau deretan angka. Beberapa algoritma pencarian yang populer meliputi “Linear Search”, “Binary Search”, “Jump Search”, “Fibonacci Search,” dll.
Apa itu Pencarian Linier?
Pencarian linier adalah salah satu algoritma pencarian paling sederhana. Dari daftar atau larik tertentu, ia mencari elemen tertentu satu per satu. Pencarian Linier mengulangi seluruh daftar dan memeriksa apakah ada elemen tertentu yang sama dengan elemen pencarian. Itu juga disebut pencarian berurutan.
Apa yang dilakukan Fungsi Pencarian Linier?
Array bilangan bulat diberikan sebagai “Numbers,” dan variabel “item” berisi bilangan bulat yang akan dicari.
Sekarang, algoritma Pencarian Linier dapat memberikan keluaran berikut:
- “-1”; ini berarti elemen tertentu tidak ditemukan dalam array
- Angka apa pun antara 0 hingga n-1; berarti elemen pencarian ditemukan, dan mengembalikan indeks elemen pada array. Di sini, “n” mewakili ukuran array.
Bagaimana cara kerja Pencarian Linier?
Katakanlah sebuah array berisi bilangan bulat. Tugasnya adalah menemukan nomor tertentu dalam array.
- Jika nomor tersebut terletak di dalam array, kita perlu mengembalikan indeks nomor tersebut.
- Jika nomor yang diberikan tidak ditemukan, maka akan kembali -1.
Dalam diagram alur, “Data” adalah array bilangan bulat, “N” adalah ukuran array, dan “item” adalah nomor yang ingin kita cari dalam array.
Diagram Alir Algoritma Pencarian Linier:
Berikut langkah-langkah flowchartnya:
Langkah 1) Baca item pencarian, “item.”
Langkah 2) Mulai i=0 dan indeks=-1
Langkah 3) Jika saya
Langkah 4) Jika Data[i] sama dengan “item”, lanjutkan ke langkah 5. Jika tidak, lanjutkan ke langkah 6.
Langkah 5) Indeks = i (Karena item terdapat pada indeks no i). Lanjutkan ke langkah 8.
Langkah 6) saya = saya +1.
Langkah 7) Lanjutkan ke langkah 3.
Langkah 8) Berhenti.
Untuk mempermudah, kami memberikan contoh dengan array bilangan bulat. Pencarian linier juga berlaku dalam string, array objek, atau struct.
Kode Pseudo untuk Algoritma Pencarian Berurutan
function linearSearch: in →Data[], item foundAt = -1 for i in (0 to data.length): if data[i] equals item // item is found in the array // returning the index return i // item not found in the array // -1 means no item found, as negative index is not valid return -1
C++ Contoh Kode Pencarian Linier
#include < bits / stdc++.h >
using namespace std;
int linearSearch(int * arr, int item, int n) {
int idx = -1;
for (int i = 0; i < n; i++) {
if (arr[i] == item) {
idx = i;
break;
}
}
return idx;
}
int main() {
int array[] = {
1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10
};
int n = sizeof(array) / sizeof(arr[0]);
int item;
cout << "Enter a number to search: ";
cin >> item;
int idx = linearSearch(arr, item, n);
if (idx >= 0) {
cout << item << " is found at index " << idx << endl;
} else {
cout << "Could not find " << item << " in the array" << endl;
}
}
Keluaran:
Enter a number to search: -10 -10 is found at index 14
Python Contoh Kode Pencarian Linier
def linearSearch(data, item):
for i in range(len(data)):
if data[i] == item:
return i
return -1
data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
print("{} is found at index {}".format(item, idx))
else :
print("{} was not found".format(item))
Keluaran:
Enter a number to search: -10 -10 is found at index 14
Analisis Kompleksitas Algoritma Pencarian Linier
Secara umum, kompleksitas waktu berarti jumlah waktu CPU untuk melakukan tugas tertentu. Dalam algoritma pencarian linear, tugasnya adalah menemukan kunci pencarian dari elemen array.
Tiga jenis kompleksitas waktu adalah:
- Skenario Kasus Terburuk
- Skenario Kasus Terbaik
- Skenario Kasus Rata-rata
Kompleksitas Waktu Pencarian Linear dalam Skenario Terburuk:
Katakanlah, kita perlu melakukan pencarian linier dalam array dengan ukuran “n”. Kita dapat menemukan item pencarian antara indeks 0 hingga n-1. Skenario terburuk, algoritma akan mencoba mencocokkan semua elemen dari array dengan elemen pencarian.
Dalam kasus tersebut, kompleksitas terburuk akan menjadi O(n). Di sini, Notasi O besar “O” berarti fungsi kompleksitas.
Kompleksitas Waktu Pencarian Linier dalam Skenario Kasus Terbaik:
Misalkan kita mencari elemen yang berada di posisi pertama pada array. Dalam skenario ini, algoritma pencarian linear tidak akan mencari semua n elemen dalam array. Jadi kompleksitasnya akan menjadi O(1). Ini berarti waktu yang konstan.
Kompleksitas Waktu Pencarian Linear dalam Skenario Kasus Rata-rata:
Bila suatu elemen ditemukan pada indeks tengah array, maka dapat dikatakan bahwa kompleksitas kasus rata-rata untuk pencarian linear adalah O(N), di mana N berarti panjang array.
Kompleksitas ruang dari algoritma pencarian linier
Kompleksitas ruang untuk pencarian linier selalu O(N) karena kita tidak perlu menyimpan atau menggunakan variabel sementara apa pun dalam fungsi pencarian linier.
Bagaimana meningkatkan Algoritma Pencarian Linier
Pencarian dapat dilakukan beberapa kali selama siklus hidup program. Ada kemungkinan juga kita menjalankan algoritma pencarian linear dan mencari kunci tertentu beberapa kali. Kita dapat menggunakan “Algoritma Pencarian Biner” jika arraynya adalah array yang diurutkan.
Asumsikan array terdiri dari 10 ribu angka, dan elemen target ditemukan pada indeks ke-5000. Jadi, algoritma akan mencoba membandingkan 5000 elemen. Sekarang, perbandingan adalah tugas yang membebani CPU. Untuk mengoptimalkan algoritma pencarian linier, kami memiliki dua opsi.
- pengangkutan
- Pindah ke Depan
Transposisi:
Dalam metode ini, kita akan menukar elemen pencarian dengan elemen sebelumnya dalam array. Misalnya, katakanlah Anda memiliki array seperti berikut:
Data[] = {1,5,9,8,7,3,4,11}
Sekarang, kami ingin mencari 4. Langkah Transposisi:
Langkah 1) “4” terdapat pada indeks 6. Dibutuhkan enam perbandingan.
Langkah 2) Tukar data[6] dan data[5]. Maka susunan datanya akan terlihat seperti:
Data[] = {1,5,9,8,7,4,3,11}
Langkah 3) Cari 4 lagi. Ditemukan pada indeks 5. Kali ini dibutuhkan lima perbandingan.
Langkah 4) Tukar data [5] dan data[4]. Maka susunan datanya akan terlihat seperti ini:
Data [] = {1,5,9,8,4,7,3,11}
Sekarang, jika Anda perhatikan, semakin sering suatu kunci dicari, semakin besar pula penurunan indeksnya. Dengan demikian, mengurangi jumlah perbandingan.
Pindah ke depan:
Dalam metode ini, kami menukar elemen pencarian di indeks ke-0. Karena jika dicari lagi, kita dapat menemukannya pada waktu O(1).
Penerapan Algoritma Pencarian Linier
Berikut beberapa aplikasi pencarian linier yang bisa kita gunakan.
- Untuk array berukuran kecil atau hanya beberapa elemen dalam daftar, lebih mudah menggunakan pencarian linier.
- Metode pencarian linier dapat digunakan secara tunggal atau array multidimensi atau struktur data lainnya.
- Umumnya, pencarian linier sederhana dan efisien untuk melakukan pencarian pada data “tidak berurutan”. Kita dapat mengambil satu data dari daftar tidak berurutan yang diberikan dengan mudah.
