Algoritma - Langkau Carian

Sebagai contoh, katakan kita mempunyai array arr[] bersaiz n dan blok (untuk dilompat) bersaiz m. Kemudian kita mencari indeks arr[0], arr[m], arr[2m]... ..arr[km] dan seterusnya. Sebaik sahaja kita menemui selang (arr[km]

Kami mempertimbangkan tatasusunan berikut: (0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610). Panjang tatasusunan ialah 16. Carian langkau akan menemui 55 dalam langkah berikut, dengan mengandaikan saiz blok yang akan dilangkau ialah 4.

Langkah 1: Lompat dari indeks 0 ke indeks 4;
Langkah 2: Lompat dari indeks 4 ke indeks 8;
Langkah 3: Lompat dari indeks 8 ke indeks 16;
Langkah 4: Memandangkan elemen pada indeks 16 lebih besar daripada 55, kami akan kembali satu langkah ke indeks 9.
Langkah 5: Lakukan carian linear dari indeks 9 untuk mendapatkan elemen 55.
Apakah saiz ketulan optimum untuk dilangkau?
Dalam kes yang paling teruk kita perlu melakukan lompatan n/m dan melakukan perbandingan m-1 dengan carian linear jika nilai yang disemak terakhir adalah lebih besar daripada elemen yang dicari. Oleh itu, jumlah bilangan perbandingan kes terburuk ialah ((n/m) + m-1). Apabila m =√n, nilai fungsi ((n/m) + m-1) akan menjadi nilai minimum. Oleh itu, saiz langkah terbaik ialah m = √n.

// C++ program to implement Jump Search

#include <bits>
using namespace std;

int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);

// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] = n)
return -1;
}

// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] 
<p>Keluaran: </p>
<p>Nombor 55 berada pada indeks 10</p>
<p>Kerumitan masa: O(√n)<br>
Ruang tambahan: O(1)</p>
<p><strong>Perhatian:</strong></p>
<p>Carian ini hanya berfungsi pada tatasusunan yang diisih. <br>
Saiz optimum ketulan untuk dilangkau ialah O(√n). Ini menjadikan carian lompat O(√n) kerumitan masa. <br>
Kerumitan masa carian langkau adalah antara carian linear ((O(n))) dan carian binari (O(Log n) <br>
Carian binari adalah lebih baik daripada carian lompat, tetapi carian lompat mempunyai kelebihan yang kita lalui sekali sahaja (carian binari mungkin memerlukan paling banyak lompatan 0 (Log n), memandangkan elemen yang dicari adalah elemen terkecil atau kurang daripada terkecil). Oleh itu, dalam sistem yang melompat ke belakang adalah mahal, kami menggunakan Carian Lompat. </p></bits>

Atas ialah kandungan terperinci Algoritma - Langkau Carian. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!