algorithms.searching module

Searching Module

The Searching Module in Algo Spectrum provides implementations of various searching algorithms, each designed to efficiently locate elements within an array or other collection.

Algorithms Included

1. Linear Search [algorithms.searching.linear_search()]

2. Sentinel Search: [algorithms.searching.sentinel_linear_search()]

3. Binary Search: [algorithms.searching.binary_search()]

4. Jump Search: [algorithms.searching.jump_search()]

5. Interpolation Search: [algorithms.searching.interpolation_search()]

6. Exponential Search: [algorithms.searching.exponential_search()]

7. Fibonacci Search: [algorithms.searching.fibonacci_search()]

8. Ternary Search: [algorithms.searching.ternary_search()]

algorithms.searching.binary_search(target: Any, items: List[Any]) → int | None

Binary search quickly finds a target value within a sorted collection by repeatedly dividing the search space in half, resulting in logarithmic time complexity.

Parameters:

• target (Any) – The value to search for.

• items (List[Any]) – The list of items to search.

Returns:

The index of the target if found, or None if not present.

Return type:

Optional[int]

algorithms.searching.exponential_search(target: Any, items: List[Any]) → int | None

Perform exponential search to find the index of the target element in the given sorted array.

Parameters:

• target (Any) – The value to search for.

• items (List[Any]) – The list of items to search.

Returns:

The index of the target if found, or None if not present.

Return type:

Optional[int]

algorithms.searching.fibonacci_search(target: int, items: List[int]) → int | None

Perform fibonacci search to find the index of the target element in the given sorted array.

Parameters:

• target (int) – The value to search for.

• items (List[int]) – The list of items to search.

Returns:

The index of the target if found, or None if not present.

Return type:

Optional[int]

algorithms.searching.interpolation_search(target: int | float | complex, items: List[int | float | complex]) → int | None

Perform Interpolation Search to find the index of the target element in the given sorted array.

Interpolation search is an algorithm for finding a specific value within an array that is sorted in ascending order. It works by making a linear interpolation to estimate the position of the target value within the array, then performs binary search in the estimated range. This algorithm is most effective when the elements in the array are uniformly distributed.

Parameters:

• target (int | float | complex) – The value to search for.

• items (List[int | float | complex]) – The list of items to search.

Returns:

The index of the target if found, or None if not present.

Return type:

Optional[int]

algorithms.searching.jump_search(target: Any, items: List[Any]) → int | None

Perform Jump Search to find the index of the target element in the given sorted array.

It works on the principle of linear search but improves the efficiency by jumping a fixed number of steps ahead in each iteration, thus reducing the number of comparisons. This algorithm requires the array to be sorted beforehand.

Parameters:

• target (Any) – The target element to search for.

• items (List[Any]) – The sorted list or array to search in.

Returns:

The index of the target element if found, else None.

Return type:

Optional[int]

algorithms.searching.linear_search(target: Any, items: List[Any]) → int | None

Linear search sequentially scans through a collection, comparing each element with the target value until a match is found or the end of the collection is reached, making it suitable for small or unsorted datasets.

Parameters:

• target (Any) – The value to search for.

• items (Any) – The list of items to search.

Returns:

The index of the target if found, or None if not present.

Return type:

Optional[int]

algorithms.searching.sentinel_linear_search(target: Any, items: List[Any]) → int | None

Sentinel linear search optimizes the standard linear search algorithm by reducing comparisons within the loop, enhancing its efficiency for searching unsorted collections.

Parameters:

• target (Any) – The value to search for.

• items (Any) – The list of items to search.

Returns:

The index of the target if found, or None if not present.

Return type:

Optional[int]

algorithms.searching.ternary_search(target: Any, items: List[Any]) → int | None

Perform ternary search to find the index of the target element in the given sorted array.

Parameters:

• target (Any) – The value to search for.

• items (List[Any]) – The list of items to search.

Returns:

The index of the target if found, or None if not present.

Return type:

Optional[int]