Jump Search algoritmus magyarázata

Ugrás keresés

Az ugrás keresés megkeres egy elemet egy rendezett tömbben k itens ugrásával, majd ellenőrizze, hogy a kívánt elem az előző ugrás és az aktuális ugrás között van-e.

Bonyolultság legrosszabb eset

O (√N)

Hogyan működik

  1. Határozza meg k értékét, az ugrás számát: Az optimális ugrási méret √N, ahol N a tömb hossza
  2. Ugrás a tömb k-by-k keresése feltétel szerint Array[i] < valueWanted < Array[i+k]
  3. Végezzen lineáris keresést Array[i]és és közöttArray[i + k]
Ugró keresés 1

Kód

A módszer kód implementációjának példáinak megtekintéséhez nyissa meg az alábbi linket:

Jump Search - OpenGenus / cosmos

Hitelek

A logika tömb képe