Algoritma linear search dan Binary search

Linear Search merupakan sebuah teknik pencarian data dengan menelusuri semua data satu per satu. Apabila ditemukan kecocokan data maka program akan mengembalikan output, jika tidak pencarian akan terus berlanjut hingga akhir dari array tersebut. Algoritma ini tidak cocok untuk set data dengan jumlah besar karena kompleksitas dari algorithma ini adalah Ο(n) di mana n adalah jumlah item. Jika data yang dicari berada pada paling akhir dari array, maka program harus menelusuri semua array terlebih dahulu.

Misalkan angka yang dicari adalah angka 40, berikut gambaran dari implementasi LinearSearch:

1st Cycle:
(70, 60, 30, 50, 40,20)
(70==40) //FALSE

2nd Cycle:
(70, 60, 30, 50, 40,20)
(60==40) //FALSE

3rd Cycle:
(70, 60, 30, 50, 40,20)
(30==40) //FALSE

4th Cycle:
(70, 60, 30, 50, 40,20)
(50==40) //FALSE

5th Cycle:
(70, 60, 30, 50, 40,20)
(40==40) //TRUE

Jika data ditemukan, maka program akan keluar dari looping. Jika kita ingin menampilkan index dari data yang dicari, kita tinggal menyimpan index dari array tersebut dan menampilkan nya.

Berikut implementasi dari Linear Search menggunakan Bahasa C:

#include <stdio.h>

int main()

{

int arr[]={70, 60, 30, 50, 40, 20};

int n = sizeof(arr)/sizeof(int);

int index=-1; //index array mulai dari 0, maka di set -1

int find=40;

for(int i=0;i<n;i++){

if(arr[i]==find){ //linear search

index=i;

break;

}

if(index==-1){

printf(“Data tidak ditemukan\n”);

}

else{

printf(“Data berada pada index ke-%d\n”,index);

}

return 0;

}

Reference:

Paul Deitel & Harvey Deitel. (2016). C how to program : with an introduction to C++. 08. Pearson Education. Hoboken. ISBN: 9780133976892.

Published at : 26 December 2019

Pencarian Biner vs Pencarian Linear

Pencarian linear, juga dikenal sebagai pencarian sekuensial adalah algoritma pencarian paling sederhana. Itu mencari nilai yang ditentukan dalam daftar dengan memeriksa setiap elemen dalam daftar. Pencarian biner juga merupakan metode yang digunakan untuk menemukan nilai yang ditentukan dalam daftar yang diurutkan. Metode pencarian biner membagi dua jumlah elemen yang diperiksa (dalam setiap iterasi), mengurangi waktu yang dibutuhkan untuk menemukan item yang diberikan dalam daftar.

Apa itu Pencarian Linear?

Pencarian linear adalah metode pencarian paling sederhana, yang memeriksa setiap elemen dalam daftar secara berurutan hingga menemukan elemen yang ditentukan. Input ke metode pencarian linier adalah urutan (seperti array, koleksi atau string) dan item yang perlu dicari. Outputnya benar jika item yang ditentukan dalam urutan yang disediakan atau salah jika tidak dalam urutan. Karena metode ini memeriksa setiap item dalam daftar sampai item yang ditentukan ditemukan, dalam kasus terburuk akan melewati semua elemen dalam daftar sebelum menemukan elemen yang diperlukan. Kompleksitas pencarian linear adalah o (n). Oleh karena itu dianggap terlalu lambat untuk digunakan ketika mencari elemen dalam daftar besar. Tetapi ini sangat sederhana dan lebih mudah diimplementasikan.

Apa itu Pencarian Biner?

Pencarian biner juga merupakan metode yang digunakan untuk menemukan item tertentu dalam daftar yang diurutkan. Metode ini dimulai dengan membandingkan elemen yang dicari dengan elemen di bagian tengah daftar. Jika perbandingan menentukan bahwa kedua elemen sama, metode akan berhenti dan mengembalikan posisi elemen. Jika elemen yang dicari lebih besar daripada elemen tengah, itu memulai metode lagi menggunakan hanya bagian bawah daftar yang diurutkan. Jika elemen yang dicari kurang dari elemen tengah, itu memulai metode lagi menggunakan hanya bagian atas daftar diurutkan. Jika elemen yang dicari tidak ada dalam daftar, metode akan mengembalikan nilai unik yang menunjukkan hal itu. Oleh karena itu metode pencarian biner membagi dua jumlah elemen yang dibandingkan (dalam setiap iterasi), tergantung pada hasil perbandingan. Akibatnya, pencarian biner berjalan dalam waktu logaritmik yang menghasilkan o (log n) kinerja kasus rata-rata.

Apa perbedaan antara Pencarian Biner dan Pencarian Linear?

Meskipun pencarian linear dan pencarian biner adalah metode pencarian, mereka memiliki beberapa perbedaan. Sementara pencarian biner beroperasi pada daftar yang diurutkan, pencarian liner dapat beroperasi pada daftar yang tidak disortir juga. Menyortir daftar umumnya memiliki kerumitan kasus rata-rata n log n. pencarian linear sederhana dan mudah diterapkan daripada pencarian biner. Tapi, pencarian linier terlalu lambat untuk digunakan dengan daftar besar karena kinerja kasus rata-rata. Di sisi lain, pencarian biner dianggap sebagai metode yang lebih efisien yang dapat digunakan dengan daftar besar. Tetapi menerapkan pencarian biner bisa sangat rumit dan sebuah penelitian telah menunjukkan bahwa kode yang akurat untuk pencarian biner dapat ditemukan hanya dalam lima dari dua puluh buku.

Linear search adalah algoritma pencarian nilai tertentu pada sebuah array/list. Algoritma pencarian ini melibatkan pemeriksaan nilai elemen pada list satu demi satu dari ujung list. Karena mekanisme kerjanya, algoritma ini juga dikenal juga dengan nama lain sequential search. Algoritma ini cocok digunakan pada array/list dengan nilai yang tidak terurut. Untuk array/list terurut, akan lebih efisien bila menggunakan binary search.

Teknik implementasi algoritma ini dalam bahasa pemrograman python cukup sederhana. Pada artikel ini diperlihatkan dua teknik linear search yakni linear search biasa yang menggunakan for loop, dan sentinel linear search yang menggunakan while loop.

Linear search dengan for loop

Untuk cara ini, perhatikan dan jalankan kode di bawah, kemudian baca penjelasan atas kode tersebut.

Penjelasan:

Baris pertama adalah deklarasi list dengan isi beberapa elemen.
Baris kedua berisi elemen yang dicari.
Variabel idx pada baris ketiga untuk menandai posisi elemen bila ditemukan. Variabel ini diisi dengan nilai awal -1.
Perintah perulangan pada baris 5 s.d 8 memeriksa tiap elemen pada list, kemudian setelah elemen ditemukan idx diisi dengan nilai i (indeks saat ini) dan perulangan dihentikan dengan perintah break.
Pada baris 10 s.d 13, jika idx masih terisi dengan nilai -1, berarti nilai yang dicari tidak ditemukan pada list. Sebaliknya, berarti nilai yang dicari ditemukan pada indeks yang sama dengan nilai idx.

Linear search dengan sentinel

Penggunaan sentinel pada algoritma ini pada dasarnya adalah cara untuk memastikan perulangan berhenti tanpa melewati elemen terakhir (out of bound), namun tanpa memerlukan pemeriksaan apakah indeks terakhir sudah terlewati, sehingga mengurangi beban perbandingan pada setiap iterasi. Hal ini dimungkinkan dengan menjadikan elemen yang dicari sebagai sentinel pada ujung array, yang secara praktis akan menghentikan perulangan jika sudah sampai pada posisi sentinel dimaksud (ujung array).

Implementasi sentinel linear search pada python dapat dilihat pada pada cuplikan kode di bawah ini. Perhatikan bahwa baris ke-4 elemen yang dicari ditambahkan sebagai sentinel dengan perintah append ke ujung akhir list.

Semoga bermanfaat,

Salam

Linear Search memeriksa item sampai menemukan nilai yang dicari.

Efisiensi: O(n)

Contoh Kode Python:

test_list = [1, 3, 9, 11, 15, 19, 29] test_val1 = 25 test_val2 = 15 def linear_search(input_array, search_value): index = 0 while (index < len(input_array)) and (input_array[index] < search_value): index += 1 if index >= len(input_array) or input_array[index] != search_value: return -1 return index print linear_search(test_list, test_val1) print linear_search(test_list, test_val2)

Binary Search menemukan elemen tengah array. Periksa bahwa nilai tengah lebih besar atau lebih rendah dari nilai pencarian. Jika lebih kecil, ia mendapat sisi kiri array dan menemukan elemen tengah bagian itu. Jika lebih besar, dapatkan bagian kanan array. Itu loop operasi sampai menemukan nilai yang dicari. Atau jika tidak ada nilai dalam array selesai pencarian.

Efisiensi: O(logn)

Contoh Kode Python:

test_list = [1, 3, 9, 11, 15, 19, 29] test_val1 = 25 test_val2 = 15 def binary_search(input_array, value): low = 0 high = len(input_array) - 1 while low <= high: mid = (low + high) / 2 if input_array[mid] == value: return mid Elif input_array[mid] < value: low = mid + 1 else: high = mid - 1 return -1 print binary_search(test_list, test_val1) print binary_search(test_list, test_val2)

Anda juga dapat melihat informasi yang divisualisasikan tentang Pencarian Linear dan Biner di sini: https://www.cs.usfca.edu/~galles/visualization/Search.html