Binary Search (Pencarian Biner)
Terakhir diperbarui
Binary search adalah algoritma untuk mencari nilai target di array yang **terurut** dengan terus membagi dua jendela pencarian. Algoritma ini membandingkan elemen tengah dengan target: jika cocok, pencarian selesai; jika tidak, separuh yang tidak mungkin berisi target dibuang dan jendela menyusut ke separuh lainnya. Setiap perbandingan membuang separuh elemen yang tersisa, itulah sebabnya algoritma ini berjalan dalam O(log n): mencari di antara sejuta nilai terurut butuh paling banyak sekitar 20 perbandingan.
Animasi di atas menampilkan pointer lo, mid, dan hi, lalu meredupkan separuh yang dibuang setelah setiap perbandingan. Satu syarat yang tidak bisa ditawar: array harus sudah terurut. Untuk data yang tidak terurut, kamu butuh linear search atau mengurutkannya dulu (lihat merge sort). Ide membagi dua yang sama juga menjadi dasar binary search tree.
Kompleksitas waktu dan ruang
| Kasus | Kompleksitas | Catatan |
|---|---|---|
| Kasus terbaik | O(1) | Elemen tengah adalah target pada perbandingan pertama. |
| Kasus rata-rata | O(log n) | Setiap perbandingan membagi dua jendela yang tersisa. |
| Kasus terburuk | O(log n) | Jendela menyusut hingga satu elemen sebelum cocok atau gagal. |
| Ruang | O(1) | Versi iteratif hanya menyimpan indeks lo, hi, dan mid. |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Atur lo ke indeks pertama dan hi ke indeks terakhir array yang terurut. |
| 2 | Hitung indeks tengah: mid = (lo + hi) // 2. |
| 3 | Jika a[mid] sama dengan target, kembalikan mid (ditemukan). |
| 4 | Jika a[mid] **lebih kecil** daripada target, target hanya mungkin ada di separuh kanan: atur lo = mid + 1. |
| 5 | Jika a[mid] **lebih besar** daripada target, cari di separuh kiri: atur hi = mid - 1. |
| 6 | Ulangi dari langkah 2 selama lo <= hi; jika jendela kosong, target tidak ada di dalam array. |
Contoh penerapan
Mencari 5 di [1, 2, 3, 5, 7, 8, 9]:
| Putaran | Jendela (lo..hi) | mid | a[mid] | Aksi |
|---|---|---|---|---|
| 1 | [1, 2, 3, 5, 7, 8, 9] (0..6) | 3 | 5 | a[3] = 5: target ditemukan di indeks 3. |
Pencarian yang gagal, langkah demi langkah
Mencari 4 di array yang sama menunjukkan bagaimana jendela menjadi kosong:
| Putaran | Jendela (lo..hi) | mid | a[mid] | Aksi |
|---|---|---|---|---|
| 1 | 0..6 | 3 | 5 | 5 > 4: cari di separuh kiri, hi = 2. |
| 2 | 0..2 | 1 | 2 | 2 < 4: cari di separuh kanan, lo = 2. |
| 3 | 2..2 | 2 | 3 | 3 < 4, jadi lo menjadi 3 dan jendela kosong: tidak ditemukan. |
Kapan memakai binary search
| Pakai saat | Hindari saat |
|---|---|
| Datanya sudah terurut (atau kamu mencarinya berkali-kali) | Datanya tidak terurut dan hanya dicari sekali (mengurutkannya dulu berbiaya O(n log n)) |
| Koleksinya mendukung akses acak yang cepat (array) | Kamu hanya punya akses berurutan (linked list) |
Datanya besar (O(log n) unggul pada skala besar) | Datanya sangat kecil (pemindaian sederhana sama cepatnya dan lebih sederhana) |
Kode Binary Search
Implementasi Binary Search yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C, Pseudocode. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Binary Search dalam Python
Python
1def binary_search(a, target):2 lo, hi = 0, len(a) - 13 while lo <= hi:4 mid = (lo + hi) // 25 if a[mid] == target:6 return mid7 if a[mid] < target:8 lo = mid + 1 # search the right half9 else:10 hi = mid - 1 # search the left half11 return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9] # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))Kode Binary Search dalam JavaScript
JavaScript
1function binarySearch(a, target) {2 let lo = 0;3 let hi = a.length - 1;4 while (lo <= hi) {5 const mid = Math.floor((lo + hi) / 2);6 if (a[mid] === target) return mid;7 if (a[mid] < target) {8 lo = mid + 1; // search the right half9 } else {10 hi = mid - 1; // search the left half11 }12 }13 return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));Kode Binary Search dalam Java
Java
1public class Main {2 static int binarySearch(int[] a, int target) {3 int lo = 0;4 int hi = a.length - 1;5 while (lo <= hi) {6 int mid = (lo + hi) / 2;7 if (a[mid] == target) return mid;8 if (a[mid] < target) {9 lo = mid + 1; // search the right half10 } else {11 hi = mid - 1; // search the left half12 }13 }14 return -1;15 }16
17 public static void main(String[] args) {18 int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19 System.out.println("Index of 5: " + binarySearch(nums, 5));20 System.out.println("Index of 4: " + binarySearch(nums, 4));21 }22}Kode Binary Search dalam C++
C++
1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5 int lo = 0;6 int hi = static_cast<int>(a.size()) - 1;7 while (lo <= hi) {8 int mid = lo + (hi - lo) / 2;9 if (a[mid] == target) return mid;10 if (a[mid] < target) {11 lo = mid + 1; // search the right half12 } else {13 hi = mid - 1; // search the left half14 }15 }16 return -1;17}18
19int main() {20 std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21 std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22 std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23 return 0;24}Kode Binary Search dalam C
C
1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4 int lo = 0;5 int hi = n - 1;6 while (lo <= hi) {7 int mid = lo + (hi - lo) / 2;8 if (a[mid] == target) return mid;9 if (a[mid] < target) {10 lo = mid + 1; /* search the right half */11 } else {12 hi = mid - 1; /* search the left half */13 }14 }15 return -1;16}17
18int main(void) {19 int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20 int n = sizeof(nums) / sizeof(nums[0]);21 printf("Index of 5: %d\n", binary_search(nums, n, 5));22 printf("Index of 4: %d\n", binary_search(nums, n, 4));23 return 0;24}Kode Binary Search dalam Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14 DECLARE lo : INTEGER15 DECLARE hi : INTEGER16 DECLARE mid : INTEGER17 lo ← 118 hi ← n19 WHILE lo <= hi DO20 mid ← (lo + hi) DIV 221 IF nums[mid] = target THEN22 RETURN mid23 ENDIF24 IF nums[mid] < target THEN25 // Target is larger, search the right half26 lo ← mid + 127 ELSE28 // Target is smaller, search the left half29 hi ← mid - 130 ENDIF31 ENDWHILE32 RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)FAQ Binary Search
Berapa kompleksitas waktu binary search?
O(log n) pada kasus rata-rata dan terburuk, karena setiap perbandingan membagi dua jendela pencarian yang tersisa, dan O(1) pada kasus terbaik saat elemen tengah pertama adalah target. Versi iteratif memakai ruang tambahan O(1).Mengapa binary search membutuhkan array yang terurut?
Langkah membagi dua bergantung pada urutan: membandingkan target dengan elemen tengah hanya memberi tahu separuh mana yang harus dibuang jika semua elemen di kiri tengah lebih kecil dan semua elemen di kanannya lebih besar. Pada data yang tidak terurut, kesimpulan itu tidak berlaku, jadi pakai linear search atau urutkan datanya dulu.
Apa perbedaan binary search dan linear search?
Linear search memindai elemen satu per satu (
O(n)) dan bekerja pada array apa pun; binary search membagi dua jendela pencarian array yang terurut (O(log n)), tetapi membutuhkan input yang terurut. Untuk beberapa item saja, perbedaannya tidak terasa; pada skala besar, binary search menang telak.Berapa banyak perbandingan yang dibutuhkan binary search?
Paling banyak sekitar
log2(n) + 1: 10 perbandingan mencakup 1.000 elemen, 20 perbandingan mencakup 1.000.000. Pertumbuhan logaritmik itulah yang menjadikannya cara pencarian bawaan pada data terurut.Apa bug overflow klasik pada binary search?
Menghitung titik tengah sebagai
(lo + hi) / 2 bisa membuat integer berukuran tetap overflow saat lo + hi melebihi nilai maksimum tipenya. Bentuk yang aman adalah mid = lo + (hi - lo) / 2. Di Python hal ini tidak masalah (integer berpresisi bebas), tetapi di Java/C/C++ ini adalah bug yang nyata dan terkenal.Apakah binary search sama dengan binary search tree?
Keduanya memakai ide membagi dua yang sama, tetapi strukturnya berbeda: binary search adalah algoritma pada array terurut, sedangkan binary search tree adalah struktur data bertaut yang menjaga key-nya tetap berurutan sehingga pencarian turun ke kiri atau ke kanan di setiap node.
Sumber terkait
Visualisasi lainnya
