Pencarian Linier: Python, C++ Example

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 larik angka. Beberapa algoritma pencarian populer meliputi "Pencarian Linier", "Pencarian Biner", "Pencarian Lompatan", "Pencarian Fibonacci", dan lain-lain.

Apa itu Pencarian Linier?

Pencarian Linier adalah salah satu algoritma pencarian paling sederhana. Dari daftar atau larik yang diberikan, algoritma ini mencari elemen yang diberikan satu per satu. Pencarian Linier mengulangi seluruh daftar dan memeriksa apakah elemen tertentu sama dengan elemen yang dicari. Algoritma ini juga disebut sebagai 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 yang diberikan 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?

Misalkan kita memiliki sebuah array yang berisi bilangan bulat. Tugasnya adalah menemukan bilangan tertentu dalam array tersebut.

• 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) Inisialisasi 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 ditemukan pada indeks nomor 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.

Pseudo Code untuk Algoritma Pencarian Sekuensial

Pseudokode berikut menggambarkan logika pencarian linier yang dijelaskan di atas. Pseudokode ini menelusuri array dari indeks pertama dan mengembalikan posisi jika ditemukan kecocokan, jika tidak, mengembalikan -1.

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 a negative index is not valid
    return -1

C++ Code Contoh Pencarian Linier

Berikut ini adalah penjelasan lengkapnya. C++ Program yang mengimplementasikan pencarian berurutan dan mencetak indeks dari nilai yang dicari.

#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(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, 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 Code Contoh Pencarian Linier

Logika yang sama dalam Python menggunakan satu perulangan pada indeks daftar dan mengembalikan posisi elemen yang cocok.

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 yang dibutuhkan untuk melakukan tugas tertentu. Dalam algoritma pencarian linier, tugasnya adalah menemukan kunci pencarian dari elemen-elemen dalam array.

Tiga jenis kompleksitas waktu adalah:

• Skenario Kasus Terburuk
• Skenario Kasus Terbaik
• Skenario Kasus Rata-rata

Kompleksitas Waktu Pencarian Linear dalam Skenario Terburuk:

Misalkan kita perlu melakukan pencarian linear dalam sebuah array dengan ukuran “n”. Kita dapat menemukan elemen yang dicari antara indeks 0 hingga n-1. Dalam skenario terburuk, algoritma akan mencoba mencocokkan semua elemen dari array dengan elemen yang dicari.

Dalam hal ini, kompleksitas kasus terburuknya adalah O(n). Di sini, “O” — Notasi Big O — berarti fungsi kompleksitas.

Kompleksitas Waktu Pencarian Linier dalam Skenario Kasus Terbaik:

Misalkan kita mencari elemen yang berada di posisi pertama array. Dalam skenario ini, algoritma pencarian linear tidak akan mencari semua n elemen dalam array. Jadi kompleksitasnya adalah O(1). Ini berarti waktu 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 sepanjang siklus hidup program. Ada kemungkinan juga kita menjalankan algoritma pencarian linier 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 yang dicari dengan elemen sebelumnya dalam array. Misalnya, anggaplah 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 array data akan terlihat seperti ini:

Data[] = {1,5,9,8,4,7,3,11}

Nah, jika Anda perhatikan, semakin sering sebuah kata kunci dicari, semakin berkurang indeksnya. Dengan demikian, jumlah perbandingan pun berkurang.

Pindah ke depan:

Dalam metode ini, kita menukar elemen pencarian ke indeks ke-0. Karena jika dicari lagi, kita dapat menemukannya dalam 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.

Pertanyaan Umum Demo Slot