Pencarian: linear dan biner
Dua cara mencari
- Mencari berarti menemukan di mana nilai berada dalam array (atau mengatakan nilainya tidak ada).
- Pencarian linear memeriksa setiap item satu per satu. Ini bekerja pada array apa pun.
- Pencarian biner jauh lebih cepat tetapi memerlukan array terurut terlebih dahulu.
Pencarian linear
- Jelajahi dari index
0hinggan - 1, membandingkan setiap item dengan target. - Kembalikan index segera setelah Anda menemukannya. Jika Anda mencapai akhir, kembalikan
-1. - Untuk array
nitem, ini melihat hinggandarinya.
Mengapa pengurutan memungkinkan pencarian biner
- Jika array terurut, Anda bisa melompat ke tengah dan membandingkan.
- Jika tengah terlalu kecil, target harus di setengah kanan; jika terlalu besar, di setengah kiri.
- Setiap langkah membuang setengah array, sehingga sangat cepat (sekitar
log2(n)langkah).
rendah, tinggi, tengah
- Pertahankan dua batas:
low(awal) danhigh(akhir). Titik tengahnya adalahmid = low + (high - low) / 2. - Jika
a[mid]adalah target, kembalikanmid. Jikaa[mid] < target, geserlow = mid + 1; selain ituhigh = mid - 1. - Berhenti ketika
low > high— target tidak ada, jadi kembalikan-1.
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
Kesalahan umum
- Pencarian biner memerlukan array yang terurut.
- Pencarian linear memeriksa setiap elemen secara bergantian.
Sekarang Anda coba
- Untuk pencarian biner, asumsikan array sudah terurut. Gunakan
low,high, danmid. - Kembalikan
-1ketika nilai tidak ditemukan. Jangan menulismain— penguji menyediakan satu.
Pencarian linear vs pencarian biner
Pencarian biner membagi dua rentang pada setiap langkahnya.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi int linear_search(const int a[], int n, int target) agar mengembalikan indeks pertama dari target, atau -1 jika item tersebut tidak ada dalam array. Jangan tulis main.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi int binary_search(const int a[], int n, int target) untuk array terurut. Kembalikan indeks dari target, atau -1. Gunakan low, high, dan mid. Jangan tulis loop main.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi int first_negative(const int a[], int n) agar mengembalikan indeks item pertama yang lebih kecil dari 0, atau -1 jika tidak ada. Jangan tulis main.
Klik Jalankan untuk melihat output di sini.