Pencarian Interpolasi di Jawa

1. Perkenalan

Dalam tutorial ini, kita akan membahas algoritma pencarian interpolasi dan membahas pro dan kontra mereka. Selanjutnya, kami akan menerapkannya di Java dan membicarakan tentang kompleksitas waktu algoritme.

2. Motivasi

Pencarian interpolasi adalah peningkatan dari pencarian biner yang disesuaikan untuk data yang terdistribusi secara seragam.

Pencarian biner membagi dua ruang pencarian pada setiap langkah terlepas dari distribusi datanya, sehingga kompleksitas waktunya selalu O (log (n)) .

Di sisi lain, kompleksitas waktu pencarian interpolasi bervariasi tergantung pada distribusi datanya . Ini lebih cepat daripada pencarian biner untuk data terdistribusi seragam dengan kompleksitas waktu O (log (log (n))) . Namun, dalam skenario terburuk, performanya bisa seburuk O (n) .

3. Pencarian Interpolasi

Mirip dengan pencarian biner, pencarian interpolasi hanya dapat bekerja pada array yang diurutkan. Ini menempatkan probe dalam posisi yang dihitung pada setiap iterasi. Jika probe tepat pada item yang kita cari, posisinya akan dikembalikan; jika tidak, ruang pencarian akan dibatasi di sisi kanan atau kiri probe.

Perhitungan posisi probe adalah satu-satunya perbedaan antara pencarian biner dan pencarian interpolasi.

Dalam pencarian biner, posisi probe selalu menjadi item paling tengah dari ruang pencarian yang tersisa.

Sebaliknya, pencarian interpolasi menghitung posisi probe berdasarkan rumus ini:

Mari kita lihat masing-masing istilah:

  • probe : posisi probe baru akan ditetapkan ke parameter ini.
  • lowEnd : indeks item paling kiri di ruang pencarian saat ini.
  • highEnd : indeks item paling kanan di ruang pencarian saat ini.
  • data [] : larik yang berisi ruang pencarian asli.
  • item : item yang kita cari.

Untuk lebih memahami cara kerja pencarian interpolasi, mari kita tunjukkan dengan sebuah contoh.

Katakanlah kita ingin mencari posisi 84 dalam larik di bawah ini:

Panjang array adalah 8, jadi awalnya highEnd = 7 dan lowEnd = 0 (karena indeks array dimulai dari 0, bukan 1).

Pada langkah pertama, rumus posisi probe akan menghasilkan probe = 5:

Karena 84 ( item yang kita cari) lebih besar dari 73 ( item posisi probe saat ini ), langkah selanjutnya akan mengabaikan sisi kiri array dengan menetapkan lowEnd = probe + 1. Sekarang ruang pencarian hanya terdiri dari 84 dan 101. Rumus posisi probe akan menetapkan probe = 6 yang persis dengan indeks 84:

Karena barang yang kita cari ditemukan, posisi 6 akan dikembalikan.

4. Implementasi di Jawa

Sekarang setelah kita memahami cara kerja algoritme, mari terapkan di Java.

Pertama, kami menginisialisasi lowEnd dan highEnd :

int highEnd = (data.length - 1); int lowEnd = 0;

Selanjutnya, kami menyiapkan loop dan di setiap iterasi, kami menghitung probe baru berdasarkan rumus yang disebutkan di atas. Kondisi loop memastikan bahwa kita tidak keluar dari ruang pencarian dengan membandingkan item dengan data [lowEnd] dan data [highEnd] :

while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) { int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]); }

Kami juga memeriksa apakah kami telah menemukan item tersebut setelah setiap tugas penyelidikan baru .

Terakhir, kami menyesuaikan lowEnd atau highEnd untuk mengurangi ruang pencarian pada setiap iterasi:

public int interpolationSearch(int[] data, int item) { int highEnd = (data.length - 1); int lowEnd = 0; while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) { int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]); if (highEnd == lowEnd) { if (data[lowEnd] == item) { return lowEnd; } else { return -1; } } if (data[probe] == item) { return probe; } if (data[probe] < item) { lowEnd = probe + 1; } else { highEnd = probe - 1; } } return -1; }

5. Kesimpulan

Pada artikel ini, kami menjelajahi pencarian interpolasi dengan sebuah contoh. Kami juga menerapkannya di Jawa.

Contoh yang ditampilkan dalam tutorial ini tersedia di Github.