Memahami Algoritma Binary Search Di JavaScript

Dalam posting ini, saya akan membandingkan algoritma linear search (pencarian linear) dan binary search (pencarian biner). Anda akan melihat pseudocode untuk setiap algoritmanya, bersama dengan contoh dan panduan langkah demi langkah untuk mengimplementasikannya.

Pengantar

Sebagai seorang programmer, Anda perlu menemukan solusi terbaik untuk suatu masalah sehingga kode Anda tidak hanya benar tetapi juga efisien. Memilih algoritma suboptimal dapat berarti waktu penyelesaian yang lebih lama, peningkatan kompleksitas kode, atau lebih buruknya program yang crash. Anda mungkin telah menggunakan algoritma search untuk mencari item-item dalam kumpulan data. Bahasa JavaScript memiliki beberapa method, seperti find, untuk menemukan item dalam array. Namun, method ini menggunakan linear search (pencarian linier).

Algoritma linear search dimulai pada awal list dan membandingkan setiap elemen dengan search value sampai ditemukan. Ini bagus jika Anda memiliki sejumlah kecil elemen. Tetapi ketika Anda mencari di daftar besar yang memiliki ribuan atau jutaan elemen, Anda perlu cara yang lebih baik untuk menemukan item-item itu.

Ini adalah saatnya Anda akan menggunakan binary search (pencarian biner). Dalam tutorial ini, saya akan menjelaskan cara kerja binary search dan bagaimana mengimplementasikan algoritmanya dalam JavaScript. Pertama, kita akan meninjau ke algoritma linear search.

Linear Search

Saya akan mulai dengan menjelaskan cara menerapkan linear search dalam JavaScript. Kita akan membuat function yang disebut linearSearch yang menerima value yang merupakan integer atau string dan array sebagai parameter. Function ini akan mencari setiap elemen dalam array untuk value-nya dan mengembalikan (return) posisi dari value tersebut dalam array jika ditemukan. Jika nilainya tidak dalam array, maka akan mengembalikan -1. Misalnya, memanggil linearSearch(1, [3, 4, 2, 1, 5]) akan me-return 3, dan memanggil linearSearch(0, [3, 4, 2, 1, 5]) akan me-return -1.

Inilah beberapa pseudocode untuk function kita:

1:  Set found to false  
2:  Set position to −1  
3:  Set index to 0  
4:  while found is false and index < number of elements  
5:    if list[index] is equal to search value  
6:      Set found to true  
7:      Set position to index  
8:    else Add 1 to index  
9:  return position  

Implementasi JavaScript pada Linear Search

Berikut ini adalah implementasi JavaScript dari algoritma linear search:

1:  function linearSearch(value, list) {  
2:    let found = false;  
3:    let position = -1;  
4:    let index = 0;  
5:    while(!found && index < list.length) {  
6:      if(list[index] == value) {  
7:        found = true;  
8:        position = index;  
9:      } else {  
10:        index += 1;  
11:      }  
12:    }  
13:    return position;  
14:  }  

Penting untuk dicatat bahwa algoritma linear search tidak perlu menggunakan list yang diurutkan. Algoritma ini juga dapat di-customize untuk digunakan dalam skenario yang berbeda seperti mencari array dari objek berdasarkan petunjuknya.

Jika Anda memiliki array data customer yang menyertakan key untuk nama depan dan belakang, Anda bisa menguji apakah array tersebut memiliki data seorang customer dengan nama depan yang spesifik. Dalam hal ini, daripada memeriksa apakah list[index] sama dengan value pencarian kita, Anda baiknya memeriksa list[index].first.

Dalam contoh di atas, saya menggunakan function linearSearch pada array dengan 5 elemen. Dalam kasus terburuk, ketika value pencarian tidak ada dalam daftar atau di akhir daftar, function tersebut harus membuat 5 perbandingan.

Karena array kita sangat kecil, tidak perlu mengoptimalkan dengan menggunakan algoritma yang berbeda. Namun, di luar titik tertentu, tidak lagi efisien untuk menggunakan algoritma linear search, dan saat itulah menggunakan algoritma binary search akan lebih baik.

Binary Search

Bayangkan Anda memainkan permainan tebak angka. Anda diminta menebak angka antara 1 dan 100. Jika nomor Anda terlalu tinggi atau terlalu rendah, Anda akan mendapatkan petunjuk. Apa strategi Anda nantinya? Apakah Anda memilih angka secara acak? Akankah Anda mulai dengan 1, lalu 2, dan seterusnya sampai Anda menebak dengan benar? Sekalipun Anda memiliki tebakan tak terbatas, Anda perlu membuat tebakan yang benar hanya dalam beberapa upaya. Karena itu, Anda bisa mulai dengan menebak 50.

Jika angkanya lebih tinggi, Anda bisa menebak 75. Jika angkanya lebih rendah, maka itu berarti angkanya antara 50 dan 75, dan Anda akan memilih angka yang ada di tengah. Anda akan terus seperti ini sampai Anda tiba di nomor yang benar. Ini mirip dengan cara kerja binary search.

Tidak seperti linear search, binary search menggunakan daftar yang diurutkan. Untuk mencari value, pertama-tama Anda membandingkan nilai dengan elemen di tengah daftar. Jika mereka sama, nilai pencarian telah ditemukan.

Jika nilai pencarian lebih besar dari elemen tengah, Anda mencari bagian atas data. Anda kemudian membandingkan elemen tengah bagian ini dengan nilai pencarian. Atau, jika item kurang dari elemen tengah, Anda mencari di bagian bawah daftar dan membandingkan nilai tengahnya. Daftar ini berulang kali dibagi dua hingga elemen ditemukan atau tidak ada lagi item untuk dicari.

Untuk mencari 9 dalam daftar:

1:  1 2 3 4 5 6 7 8 9 10  

Pertama kali kta menemukan elemen tengah. Ini adalah elemen di posisi Math.floor((first + last)/2), di mana first adalah index pertama, dan last adalah index terakhir. Kita memilih untuk membulatkan sehingga jika hasilnya adalah fraction, itu menjadi bilangan bulat. Elemen tengah dalam daftar ini adalah 5. Nilai pencarian kita 9 lebih besar dari 5, jadi kita mencari daftar:

1:  6 7 8 9 10  

Elemen tengah dari bagian ini adalah 8. Sembilan lebih besar dari 8, jadi kita mencari daftar:

1:  9 10  

Elemen tengah adalah 9, sehingga kita dapat menghentikan pencarian kami di sini.

Berikut beberapa pseudocode yang mengekspresikan algoritma di atas untuk binary search:

1:  Set first to 0  
2:  Set last to the last index in the list  
3:  Set found to false  
4:  Set position to −1  
5:  while found is false and first is less than or equal to last  
6:    Set middle to the index halfway between first and last  
7:    if list[middle] equals the desired value  
8:      Set found to true  
9:      Set position to middle  
10:    else if list[middle] is greater than the desired value  
11:      Set last to middle − 1  
12:    else  
13:      Set first to middle + 1  
14:  return position  

Implementasi JavaScript dari Binary Search

Sekarang mari kita membuat kode algoritma binary search dalam JavaScript!

Kita akan membuat function, binarySearch, yang menerima value dan array sebagai parameter. Function ini akan mengembalikan (return) index tempat value tersebut muncul dalam daftar jika ditemukan. Jika nilainya tidak ditemukan, ia mengembalikan -1. Ini adalah implementasi kami yang ditulis dalam JavaScript:

1:  function binarySearch(value, list) {  
2:    let first = 0;  //left endpoint  
3:    let last = list.length - 1;  //right endpoint  
4:    let position = -1;  
5:    let found = false;  
6:    let middle;  
7:    while (found === false && first <= last) {  
8:      middle = Math.floor((first + last)/2);  
9:      if (list[middle] == value) {  
10:        found = true;  
11:        position = middle;  
12:      } else if (list[middle] > value) { //if in lower half  
13:        last = middle - 1;  
14:      } else { //in in upper half  
15:        first = middle + 1;  
16:      }  
17:    }  
18:    return position;  
19:  }  

Kesimpulan

Dalam tutorial ini, kita melihat bagaimana menerapkan algoritma linear search dan binary search. Algoritma linear search lebih sederhana dan tidak memerlukan array yang diurutkan. Namun, itu tidak efisien untuk digunakan dengan array yang lebih besar. Dalam kasus terburuk, algoritmanya harus mencari semua elemen yang membuat perbandingan n (di mana n adalah jumlah dari elemen-elemen yang ada).

Di sisi lain algoritma binary search mengharuskan Anda untuk mengurutkan array terlebih dahulu dan lebih rumit untuk diimplementasikan. Namun, ini lebih efisien bahkan ketika mempertimbangkan waktu penyortiran. Sebagai contoh, sebuah array dengan 10 elemen akan membuat paling banyak 4 perbandingan untuk pencarian biner vs 10 untuk pencarian linier, bukan perbaikan besar. Namun, untuk array dengan 1.000.000 elemen, kasus terburuk dalam binary search hanya 20 perbandingan. Itu peningkatan besar dibandingkan linear search!

Mengetahui cara menggunakan binary search bukan hanya sesuatu untuk berlatih untuk pertanyaan wawancara. Ini adalah keterampilan praktis yang dapat membuat kode Anda bekerja lebih efisien.