Hop-søgealgoritme forklaret

Spring søgning

En hoppesøgning lokaliserer et element i et sorteret array ved at springe k itens og derefter kontrollere, om det ønskede element er mellem det forrige spring og det aktuelle spring.

Kompleksitet Værste tilfælde

O (√N)

Hvordan det virker

  1. Definer værdien af ​​k, antallet af spring: Den optimale springstørrelse er √N hvor N er længden af ​​arrayet
  2. Spring arrayet k-for-k-søgning efter betingelsen Array[i] < valueWanted < Array[i+k]
  3. Foretag en lineær søgning mellem Array[i]ogArray[i + k]
Jumping Search 1

Kode

For at se eksempler på kodeimplementering af denne metode skal du gå til dette link nedenfor:

Jump-søgning - OpenGenus / kosmos

Kreditter

Logikens arraybillede