Searching: linear and binary · ⁨Pencarian: linear dan biner⁩ — Java for AP CS A

English

Finding a value

A common job is to search: is a value in an array, and where?
The usual answer is the index where we found it, or -1 if it is not there.
We learn two ways: linear search (works on any array) and binary search (needs a sorted array, but is much faster).

Bahasa Indonesia

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 -1 jika 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).

English

Linear search

Look at each item from index 0 to the end.
If the item equals the target, return its index right away.
If the loop finishes with no match, return -1.

Bahasa Indonesia

Pencarian linear

Lihat setiap item dari indeks 0 hingga 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
    }
}

English

How fast is linear search?

In the worst case (the value is last, or missing) it checks every item.
For a list of n items that is up to n checks. We call this linear time.
For small arrays this is totally fine. For huge sorted arrays we can do better.

Bahasa Indonesia

Seberapa cepat pencarian linear?

Dalam kasus terburuk (nilai berada di urutan terakhir atau hilang), ia memeriksa semua item.
Untuk daftar n item, itu membutuhkan hingga n pengecekan. Kita menyebut ini waktu linear.
Untuk array kecil, ini sangat baik. Untuk array terurut yang sangat besar, kita bisa melakukan lebih baik.

English

Binary search needs a sorted array

Binary search only works when the array is already sorted (small to large).
It checks the middle item, then throws away half the array each step.
That is much faster: a million items take about 20 checks, not a million.

Bahasa Indonesia

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.

English

The binary search idea

Keep two bounds: low (start) and high (end).
Look at the middle index mid = (low + high) / 2.
If a[mid] equals the target, return mid.
If a[mid] is too small, the target must be on the right, so set low = mid + 1.
If a[mid] is too big, the target must be on the left, so set high = mid - 1.
Stop when low passes high; then the value is not there, return -1.

Bahasa Indonesia

Ide pencarian biner

Jaga dua batas: low (awal) dan high (akhir).
Lihat indeks tengah mid = (low + high) / 2.
Jika a[mid] sama dengan target, kembalikan mid.
Jika a[mid] terlalu kecil, target harus ada di sisi kanan, jadi set low = mid + 1.
Jika a[mid] terlalu besar, target harus ada di sisi kiri, jadi set high = mid - 1.
Berhenti ketika low melewati high; 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
    }
}

English

When a value is missing

Both searches return -1 when the target is not in the array.
For binary search, the loop ends when low > high — the bounds have crossed, so there is nowhere left to look.
Always handle the -1 case in code that calls a search.

Bahasa Indonesia

Ketika nilai hilang

Kedua pencarian mengembalikan -1 ketika 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 -1 dalam 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
    }
}

English

Common mistakes

Binary search needs a sorted array.
Linear search is O(n); binary is O(log n).

Bahasa Indonesia

Kesalahan umum

Pencarian biner memerlukan array yang terurut.
Pencarian linear adalah O(n); pencarian biner adalah O(log n).

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

Bahasa Indonesia

Sekarang Anda coba

Setiap tugas telah mengisi kerangka class — tulis kode Anda di dalam main, atau lengkapi method yang ditampilkan.
Tekan Jalankan untuk mengompilasi dan menjalankan, lalu Periksa jawaban.
Kode Anda dikompilasi dan dijalankan di server, sehingga bahkan jalankan pertama kali pun cepat.

Explore · ⁨Jelajahi⁩

Linear vs binary search · ⁨Pencarian linear vs pencarian biner⁩

Binary search halves the range each step — far fewer checks. · ⁨Pencarian biner membagi dua jangkauan setiap langkah — jauh lebih sedikit pemeriksaan.⁩

Complete linearSearch(int[] a, int target). Return the index of the first item equal to target, or -1 if it is not in the array. Check items from index 0 upward. · ⁨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.⁩

public class SearchUtil {
    // Return the index of target, or -1 if not found.
    public static int linearSearch(int[] a, int target) {
        return -1;   // change this
    }
}

Click Run to see the output here. · ⁨Klik Jalankan untuk melihat output di sini.⁩

Complete binarySearch(int[] a, int target) for a sorted array. Use low/high bounds and check the middle each step. Return the index of target, or -1 if it is missing. · ⁨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.⁩

public class SearchUtil {
    // Binary search on a sorted array. Return index or -1.
    public static int binarySearch(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        // your loop here
        return -1;
    }
}

Click Run to see the output here. · ⁨Klik Jalankan untuk melihat output di sini.⁩

Complete countOccurrences(int[] a, int target) that returns how many times target appears in a (a linear scan). Return 0 if it never appears. · ⁨Lengkapi countOccurrences(int[] a, int target) yang mengembalikan berapa kali target muncul dalam a (pindaian linear). Kembalikan 0 jika tidak pernah muncul.⁩

public class SearchUtil {
    // Count how many times target appears in a.
    public static int countOccurrences(int[] a, int target) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨Klik Jalankan untuk melihat output di sini.⁩

Searching: linear and binary · ⁨Pencarian: linear dan biner⁩

Finding a value

Mencari nilai

Linear search

Pencarian linear

How fast is linear search?

Seberapa cepat pencarian linear?

Binary search needs a sorted array

Pencarian biner memerlukan array terurut

The binary search idea

Ide pencarian biner

When a value is missing

Ketika nilai hilang

Common mistakes

Kesalahan umum

Now you try

Sekarang Anda coba

Linear vs binary search · ⁨Pencarian linear vs pencarian biner⁩

Handout · ⁨Lembar Kerja⁩

Log in or create account · ⁨Masuk atau buat akun⁩

Your subject · ⁨Mata Pelajaran Anda⁩

All sections · ⁨Semua bagian⁩

Feedback & help · ⁨Umpan balik & bantuan⁩