searches.jump_search

Pure Python implementation of the jump search algorithm. This algorithm iterates through a sorted collection with a step of n^(1/2), until the element compared is bigger than the one searched. It will then perform a linear search until it matches the wanted number. If not found, it returns -1.

https://en.wikipedia.org/wiki/Jump_search

Attributes

T
user_input

Classes

Comparable

Base class for protocol classes.

Functions

jump_search(→ int)

Python implementation of the jump search algorithm.

Module Contents

class searches.jump_search.Comparable

Bases: Protocol

Base class for protocol classes.

Protocol classes are defined as:

class Proto(Protocol):
    def meth(self) -> int:
        ...

Such classes are primarily used with static type checkers that recognize structural subtyping (static duck-typing).

For example:

class C:
    def meth(self) -> int:
        return 0

def func(x: Proto) -> int:
    return x.meth()

func(C())  # Passes static type check

See PEP 544 for details. Protocol classes decorated with @typing.runtime_checkable act as simple-minded runtime protocols that check only the presence of given attributes, ignoring their type signatures. Protocol classes can be generic, they are defined as:

class GenProto[T](Protocol):
    def meth(self) -> T:
        ...

__lt__(other: Any, /) → bool

searches.jump_search.jump_search(arr: collections.abc.Sequence[T], item: T) → int

Python implementation of the jump search algorithm. Return the index if the item is found, otherwise return -1.

Examples: >>> jump_search([0, 1, 2, 3, 4, 5], 3) 3 >>> jump_search([-5, -2, -1], -1) 2 >>> jump_search([0, 5, 10, 20], 8) -1 >>> jump_search([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610], 55) 10 >>> jump_search([“aa”, “bb”, “cc”, “dd”, “ee”, “ff”], “ee”) 4

searches.jump_search.T

searches.jump_search.user_input