Pencarian Interpolasi di Jawa

1. Pengenalan

Dalam tutorial ini, kita akan membahas algoritma carian interpolasi dan membincangkan kebaikan dan keburukan mereka. Selanjutnya, kami akan melaksanakannya di Java dan membincangkan kerumitan masa algoritma.

2. Motivasi

Pencarian interpolasi adalah peningkatan berbanding carian binari yang disesuaikan untuk data yang diedarkan secara seragam.

Pencarian binari mengurangkan ruang carian pada setiap langkah tanpa mengira pengedaran data, oleh itu kerumitan masa selalu O (log (n)) .

Sebaliknya, kerumitan masa pencarian interpolasi berbeza-beza bergantung pada pengedaran data . Ia lebih pantas daripada pencarian binari untuk data yang diedarkan secara seragam dengan kerumitan masa O (log (log (n))) . Namun, dalam senario terburuk, ia boleh menunjukkan prestasi yang buruk seperti O (n) .

3. Pencarian Interpolasi

Sama seperti carian binari, carian interpolasi hanya dapat dijalankan pada susunan yang disusun. Ia meletakkan probe dalam kedudukan yang dikira pada setiap lelaran. Sekiranya siasatan tepat pada item yang kami cari, kedudukan akan dikembalikan; jika tidak, ruang carian akan terhad di sebelah kanan atau kiri probe.

Pengiraan kedudukan probe adalah satu-satunya perbezaan antara carian binari dan carian interpolasi.

Dalam carian binari, kedudukan probe selalu menjadi item tengah dari ruang carian yang tinggal.

Sebaliknya, carian interpolasi menghitung kedudukan probe berdasarkan formula ini:

Mari lihat setiap syarat:

  • probe : kedudukan probe baru akan diberikan kepada parameter ini.
  • lowEnd : indeks item paling kiri di ruang carian semasa.
  • highEnd : indeks item paling kanan di ruang carian semasa.
  • data [] : tatasusunan yang mengandungi ruang carian asal.
  • item : item yang kami cari.

Untuk lebih memahami bagaimana carian interpolasi berfungsi, mari kita tunjukkan dengan contoh.

Katakan kita mahu mencari kedudukan 84 dalam susunan di bawah:

Panjang array adalah 8, jadi pada mulanya highEnd = 7 dan lowEnd = 0 (kerana indeks array bermula dari 0, bukan 1).

Pada langkah pertama, formula kedudukan probe akan menghasilkan probe = 5:

Oleh kerana 84 ( item yang kita cari) lebih besar daripada 73 ( item kedudukan probe semasa ), langkah seterusnya akan meninggalkan sebelah kiri array dengan menetapkan lowEnd = probe + 1. Sekarang ruang carian hanya terdiri dari 84 dan 101. Formula kedudukan probe akan menetapkan probe = 6 yang tepat adalah indeks 84:

Oleh kerana barang yang kami cari dijumpai, kedudukan 6 akan dikembalikan.

4. Pelaksanaan di Jawa

Setelah memahami bagaimana algoritma berfungsi, mari kita laksanakan di Java.

Pertama, kita memulakan lowEnd dan highEnd :

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

Seterusnya, kami menetapkan gelung dan dalam setiap lelaran, kami mengira probe baru berdasarkan formula yang disebutkan di atas. Keadaan gelung memastikan bahawa kita tidak keluar dari ruang carian 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 sama ada kami menjumpai item tersebut setelah setiap tugasan siasatan baru .

Akhirnya, kami menyesuaikan lowEnd atau highEnd untuk mengurangkan ruang carian pada setiap lelaran:

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

Dalam artikel ini, kami meneroka carian interpolasi dengan contoh. Kami juga menerapkannya di Java.

Contoh yang ditunjukkan dalam tutorial ini terdapat di Github.