Pencarian: linear dan biner
Mencari nilai
- Tugas umum adalah melakukan pencarian: apakah ada nilai dalam array, dan di mana posisinya?
- Jawaban umumnya adalah indeks di mana kita menemukannya, atau
-1jika nilainya tidak ada. - Kita mempelajari dua cara: pencarian linear (bekerja pada array apa pun) dan pencarian biner (membutuhkan array yang terurut, tetapi jauh lebih cepat).
Pencarian linear
- Lihat setiap item dari indeks
0hingga akhir. - Jika item sama dengan target, kembalikan indeksnya segera.
- Jika perulangan selesai tanpa kecocokan, kembalikan
-1.
public class Main {
public static void main(String[] args) {
int[] a = {4, 8, 15, 16, 23};
int target = 15;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop early, we have it
}
}
System.out.println(found); // 2
}
}
Seberapa cepat pencarian linear?
- Dalam kasus terburuk (nilai berada di urutan terakhir atau hilang), ia memeriksa semua item.
- Untuk daftar
nitem, itu membutuhkan hingganpengecekan. Kita menyebut ini waktu linear. - Untuk array kecil, ini sangat baik. Untuk array terurut yang sangat besar, kita bisa melakukan lebih baik.
Pencarian biner memerlukan array terurut
- Pencarian biner hanya bekerja ketika array sudah terurut (kecil ke besar).
- Ia memeriksa item tengah, kemudian membuang setengah array setiap langkahnya.
- Itu jauh lebih cepat: satu juta item membutuhkan sekitar 20 pengecekan, bukan satu juta.
Ide pencarian biner
- Jaga dua batas:
low(awal) danhigh(akhir). - Lihat indeks tengah
mid = (low + high) / 2. - Jika
a[mid]sama dengan target, kembalikanmid. - Jika
a[mid]terlalu kecil, target harus ada di sisi kanan, jadi setlow = mid + 1. - Jika
a[mid]terlalu besar, target harus ada di sisi kiri, jadi sethigh = mid - 1. - Berhenti ketika
lowmelewatihigh; maka nilai tersebut tidak ada, kembalikan-1.
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38}; // sorted!
int target = 16;
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1; // go right
} else {
high = mid - 1; // go left
}
}
System.out.println(found); // 4
}
}
Ketika nilai hilang
- Kedua pencarian mengembalikan
-1ketika target tidak ada dalam array. - Untuk pencarian biner, perulangan berakhir ketika
low > high— batas-batas telah bersilangan, sehingga tidak ada lagi tempat untuk dicari. - Selalu tangani kasus
-1dalam kode yang memanggil fungsi pencarian.
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12}; // sorted
int target = 7; // not in the array
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println(found); // -1
}
}
Kesalahan umum
- Pencarian biner memerlukan array yang terurut.
- Pencarian linear adalah O(n); pencarian biner adalah O(log n).
Sekarang Anda coba
- Setiap tugas telah mengisi kerangka class — tulis kode Anda di dalam main, atau lengkapi method yang ditampilkan.
- Gunakan Periksa jawaban untuk mengompilasi kode Anda dengan tes yang disediakan dan lihat hasilnya. Jaga antarmuka kelas dan metode yang ditampilkan pada starter.
- Kode Anda dikompilasi dan dijalankan di server, sehingga bahkan jalankan pertama kali pun cepat.
Pencarian linear vs pencarian biner
Pencarian biner membagi dua jangkauan setiap langkah — jauh lebih sedikit pemeriksaan.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi linearSearch(int[] a, int target). Kembalikan indeks dari item pertama yang sama dengan target, atau -1 jika tidak ada dalam array. Periksa item dari indeks 0 ke atas.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi binarySearch(int[] a, int target) untuk array yang terurut. Gunakan batas low/high dan periksa tengah setiap langkah. Kembalikan indeks dari target, atau -1 jika hilang.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi countOccurrences(int[] a, int target) yang mengembalikan berapa kali target muncul dalam a (pindaian linear). Kembalikan 0 jika tidak pernah muncul.
Klik Jalankan untuk melihat output di sini.