Pencarian Linier vs Pencarian Biner: Perbedaan Antara Pencarian Linier & Pencarian Biner

Diterbitkan: 2021-02-09

Daftar isi

pengantar

Alokasi memori yang berdekatan dalam bahasa pemrograman menyediakan implementasi yang fleksibel untuk menyimpan banyak titik data. Ini dapat digunakan pada puncaknya jika kita ingin memisahkan data dan menggabungkan semua data serupa dalam struktur data yang berdekatan seperti array, daftar, dll.

Alokasi memori yang berdekatan memiliki banyak implementasi dalam aplikasi dunia nyata seperti sistem operasi di komputer, sistem manajemen basis data, dll. Struktur data ini dianggap fleksibel karena menambahkan titik data baru ke array hanya membutuhkan satu unit waktu yaitu; O(1).

Tetapi masalah muncul ketika kita ingin melihat entri tertentu atau mencari entri tertentu karena semua aplikasi dunia nyata bergantung pada perintah pengaksesan data. Dan tugas ini harus cukup cepat untuk memenuhi kecepatan prosesor dan memori.

Ada berbagai algoritma pencarian yang dibagi berdasarkan jumlah perbandingan yang kami buat untuk mencari elemen.

Jika kita membandingkan setiap titik data dalam array untuk mencari elemen, maka itu dianggap sebagai pencarian berurutan. Tetapi jika kita membandingkan hanya beberapa elemen dengan melewatkan beberapa perbandingan maka itu dianggap sebagai pencarian interval. Tetapi kita membutuhkan array dalam urutan yang diurutkan (urutan menaik atau menurun) untuk melakukan pencarian interval di atasnya.

Kompleksitas waktu pencarian sekuensial adalah linier O(n), dan kompleksitas waktu pencarian biner (contoh pencarian interval) adalah O(log n). Juga, ada algoritma pencarian lain seperti pencarian eksponensial, pencarian lompat, dll.

Tetapi pencarian linier dan pencarian biner paling banyak digunakan, di mana pencarian linier adalah untuk data acak atau tidak disortir dan pencarian biner untuk data yang diurutkan dan diurutkan. Hashing adalah algoritma pencarian khusus di mana kompleksitas waktu mengakses titik data adalah O(1).

Pertama-tama mari kita menelusuri algoritma pencarian linier dan pencarian biner dan kemudian membandingkan perbedaan antara pencarian linier dan pencarian biner.

Pencarian Linier

Seperti yang telah dibahas, algoritma pencarian linier membandingkan setiap elemen dalam array, dan inilah kode untuk melakukannya.

UpGrad kelas publik {
public static int linear_search ( int [] arr, int n, int k){
untuk ( int i= 0 ; i<n; i++)
jika (arr[i]==k)
kembali i+ 1 ;
kembali – 1 ;
}
public static void main (String[] args){
int [] arr= baru int []{ 1 , 2 , 5 , 6 , 3 , 8 , 9 , 9 , 0 , 13 , 45 , 65 };
int k= 13 ;
int n=arr.panjang;
int r=linier_search(arr, n, k);
jika (r==- 1 )
System.out.println( "elemen tidak ditemukan" );
lain
System.out.println( “elemen ditemukan pada posisi “ +r+ ” );
}
}

Mari kita menelusuri kodenya.

Kami telah mendeklarasikan fungsi linear_search, yang mengharapkan array, kunci integer sebagai parameter. Sekarang kita perlu mengulang semua elemen dan membandingkan apakah itu cocok dengan kunci pencarian kita, jadi kita telah menulis loop for yang mengulang array, dan di dalamnya, ada loop if yang memeriksa apakah nomor pada posisi itu cocok dengan tombol pencarian atau tidak. Jika kami menemukan kecocokan, kami akan mengembalikan posisinya. Jika tidak ada elemen seperti itu dalam array maka kita akan mengembalikan -1 di akhir fungsi.

Perhatikan bahwa jika kita memiliki beberapa kemunculan dari angka yang sama, maka kita akan mengembalikan posisi kemunculan pertamanya.

Datang ke metode utama, kami telah mendeklarasikan dan menginisialisasi array integer. Kemudian kita menginisialisasi kunci yang harus dicari. Di sini kami melakukan hardcoding array dan kunci, tetapi Anda dapat mengubahnya ke input pengguna. Sekarang setelah kita mendapatkan daftar elemen dan kunci yang akan dicari, metode pencarian linier dipanggil dan indeks yang dikembalikan dicatat. Kemudian kami memeriksa nilai yang dikembalikan dan mencetak indeks jika kuncinya ada, jika tidak, kunci pencetakan tidak ditemukan.

Pencarian Biner

Pencarian biner lebih dioptimalkan daripada pencarian linier, tetapi array harus diurutkan untuk menerapkan pencarian biner. Dan inilah kode untuk melakukan itu.

UpGrad kelas publik {
public static int binary_search ( int [] arr, int k){
int l= 0 ,h=arr.length- 1 ,mid= 0 ;
sementara (l<=h){
tengah=l+(hl)/ 2 ;
jika (arr[pertengahan]==k)
kembali pertengahan + 1 ;
else if (arr[mid]>k)
h=pertengahan- 1 ;
lain
l=pertengahan+ 1 ;
}
kembali – 1 ;
}
public static void main (String[] args){
int [] arr= baru int []{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
int k= 8 ;
int r=pencarian_biner(arr,k);
jika (r==- 1 )
System.out.println( "elemen tidak ditemukan" );
lain
System.out.println( “elemen ditemukan pada posisi “ +r+ ” );
}
}

Mari kita menelusuri kodenya.

Kami telah mendeklarasikan metode binary_search yang mengharapkan array integer yang diurutkan dan kunci integer sebagai parameter. Kami menginisialisasi variabel rendah, tinggi, sedang. Di sini rendah, tinggi adalah petunjuk di mana rendah akan berada pada indeks 0 dan tinggi akan berada pada indeks n di awal. Jadi bagaimana cara kerja pencarian biner?

Pada awalnya, kita akan menghitung mid of low dan high. Kita dapat menghitung pertengahan sebagai (rendah+tinggi)/2, tetapi terkadang tinggi dapat berupa angka yang besar, dan menambahkan rendah ke tinggi dapat menyebabkan luapan bilangan bulat. Jadi menghitung mid as low+(high-low)/2 akan menjadi cara yang optimal.

Kami akan membandingkan elemen di tengah dengan kunci pencarian, dan kami akan mengembalikan indeks jika kami menemukan kecocokan. Jika tidak, kita akan memeriksa apakah elemen tengah lebih besar dari kunci atau lebih kecil dari kunci. Jika mid lebih besar maka kita hanya perlu memeriksa paruh pertama larik karena semua elemen di paruh kedua larik lebih besar dari kuncinya, jadi kami akan memperbarui tinggi ke mid-1.

Demikian pula jika mid kurang dari kunci maka kita perlu mencari di paruh kedua array, maka perbarui yang rendah ke mid+1. Ingat pencarian biner didasarkan pada algoritma penurunan dan taklukkan karena kita mengabaikan salah satu bagian dari array di setiap iterasi.

Kembali ke kode kami, kami telah membangun metode utama. Menginisialisasi array yang diurutkan dan kunci pencarian, membuat panggilan ke pencarian biner, dan mencetak hasilnya.

Sekarang setelah kita mempelajari algoritma pencarian linier dan pencarian biner, mari kita bandingkan kedua algoritma.

Pencarian Linier vs Pencarian Biner

Bekerja

Pencarian linier beralih melalui semua elemen dan membandingkannya dengan kunci yang harus dicari.
Pencarian biner dengan bijak mengurangi ukuran array yang harus dicari dan membandingkan kunci dengan elemen tengah setiap saat.

Struktur data

Pencarian linier fleksibel dengan semua struktur data seperti array, daftar, daftar tertaut, dll.
Pencarian biner tidak dapat dilakukan pada semua struktur data karena kita membutuhkan traversal multi-arah. Jadi struktur data seperti daftar tertaut tunggal tidak dapat digunakan.

Prasyarat

Pencarian linier dapat dilakukan pada semua jenis data, data dapat di acak atau diurutkan dengan algoritma tetap sama. Jadi tidak perlu ada pra-pekerjaan yang harus dilakukan.
Pencarian biner hanya berfungsi pada array yang diurutkan. Jadi pengurutan array merupakan prasyarat untuk algoritma ini.

Gunakan Kasus

Pencarian linier umumnya lebih disukai untuk kumpulan data yang lebih kecil dan berurutan secara acak.
Pencarian biner lebih disukai untuk kumpulan data yang relatif lebih besar dan diurutkan.

Efektivitas

Pencarian linier kurang efisien dalam kasus kumpulan data yang lebih besar.
Pencarian biner lebih efisien dalam kasus kumpulan data yang lebih besar.

Kompleksitas Waktu

Dalam pencarian linier, kompleksitas kasus terbaik adalah O(1) di mana elemen ditemukan pada indeks pertama. Kompleksitas kasus terburuk adalah O(n) di mana elemen ditemukan pada indeks terakhir atau elemen tidak ada dalam array.
Dalam pencarian biner, kompleksitas kasus terbaik adalah O(1) di mana elemen ditemukan di indeks tengah. Kompleksitas kasus terburuk adalah O( log 2 n).

Lari Kering

Mari kita asumsikan bahwa kita memiliki array berukuran 10.000.

Dalam pencarian linier, kompleksitas kasus terbaik adalah O(1) dan kompleksitas kasus terburuk adalah O(10000).
Dalam pencarian biner, kompleksitas kasus terbaik adalah O(1) dan kompleksitas kasus terburuk adalah O( log 2 10000)=O(13,287).

Kesimpulan

Kami telah memahami pentingnya mengakses data dalam array, memahami algoritma pencarian linier dan pencarian biner. Berjalan melalui kode pencarian linier dan pencarian biner. Dibandingkan perbedaan antara pencarian linier dan pencarian biner, membuat kering menjalankan untuk contoh berukuran besar.

Sekarang setelah Anda mengetahui perbedaan antara pencarian linier dan pencarian biner, coba jalankan kedua kode untuk kumpulan data besar dan bandingkan waktu eksekusi, mulai jelajahi berbagai algoritma pencarian, dan coba terapkan!

Jika Anda penasaran untuk belajar tentang ilmu data, lihat Diploma PG IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan pakar industri, 1- on-1 dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.

Pelajari kursus ilmu data online dari Universitas top dunia. Dapatkan Program PG Eksekutif, Program Sertifikat Tingkat Lanjut, atau Program Magister untuk mempercepat karier Anda.

Bandingkan pencarian linier dan pencarian biner menggunakan kompleksitasnya.

Pencarian Biner lebih optimal dan efisien daripada Pencarian Linier dalam banyak hal, terutama ketika elemen-elemennya diurutkan. Alasannya bermuara pada kompleksitas kedua pencarian.
Pencarian Linier
1. Kompleksitas Waktu: O(N) - Karena dalam pencarian linier, kami melintasi array untuk memeriksa apakah ada elemen yang cocok dengan kuncinya. Dalam skenario terburuk, elemen akan ada di akhir larik sehingga kita harus melewati ujungnya, dan karenanya kompleksitas waktunya adalah O(N) di mana N adalah jumlah total elemen larik.
2. Kompleksitas Ruang: O(1) - Kami tidak menggunakan ruang tambahan apa pun sehingga kompleksitas ruang akan menjadi O(1).
Pencarian Biner
1. Kompleksitas Waktu: O(log N) - Dalam Pencarian Biner, pencarian berkurang menjadi setengahnya karena kita hanya perlu melihat ke tengah array. Dan kami terus-menerus mempersingkat pencarian kami ke tengah bagian di mana elemen itu ada.
2. Kompleksitas Ruang: O(1)
- Kami tidak menggunakan ruang ekstra sehingga kompleksitas ruang akan menjadi O(1).

Apakah ada metode lain untuk mencari elemen dalam array?

Meskipun pencarian linier dan pencarian biner sering digunakan untuk pencarian, memang ada metode pencarian lain - metode interpolasi. Ini adalah versi Pencarian Biner yang dioptimalkan di mana semua elemen didistribusikan secara seragam.
Ide dibalik metode ini adalah bahwa dalam pencarian biner, kita selalu melihat ke tengah array. Namun pada metode ini, pencarian dapat menuju ke lokasi yang berbeda tergantung dimana letak kunci tersebut. Misalnya, jika kunci terletak di dekat elemen terakhir larik, pencarian akan dimulai dari akhir larik.

Apa kompleksitas waktu yang berbeda dari pencarian interpolasi?

Kompleksitas waktu kasus terburuk dari pencarian interpolasi adalah O(N) karena dalam kasus terburuk, kuncinya akan berada di akhir array sehingga iterator harus melintasi seluruh array.
Kompleksitas kasus rata-rata akan menjadi O(log(log N) karena elemen dapat berada di mana saja dalam array. Mungkin juga dekat dengan titik awal.
Kompleksitas kasus terbaik adalah O(1) karena, dalam kasus terbaik, kuncinya akan menjadi elemen pertama dari array.