README
¶
retrievium
n. the practice of getting back what you put in. Also: making your slices give up their secrets.
One interface. No haystack required.
Install
go get github.com/danielriddell21/retrievium/v2@latest
Quick start
import "github.com/danielriddell21/retrievium/v2"
s := retrievium.BinarySearcher[int]{}
idx, ok := s.Search([]int{1, 3, 5, 7, 9}, 7)
// idx == 3, ok == true
fmt.Println(s.Name()) // "Binary Search"
// Searchers are generic over any cmp.Ordered type:
i, found := retrievium.BinarySearcher[string]{}.Search([]string{"apple", "kiwi", "pear"}, "kiwi")
// i == 1, found == true
Every searcher satisfies the Searcher interface, generic over the element type:
type Searcher[E cmp.Ordered] interface {
Search(haystack []E, target E) (int, bool)
Name() string
}
Search returns the index of the target and a boolean reporting whether it
was found (mirroring slices.BinarySearch). BinarySearcher, TernarySearcher,
FibonacciSearcher, and JumpSearcher require the input to be sorted in
ascending order. LinearSearcher works on any input.
Why not slices.BinarySearch?
For production code, reach for the standard library — slices.BinarySearch and
slices.Index are the right tool. retrievium exists for teaching and
exploration: a single interface that lets you swap in and compare a family of
search algorithms at runtime.
Algorithms
| Searcher | Time | Space | Requires sorted input |
|---|---|---|---|
LinearSearcher |
O(n) | O(1) | No |
BinarySearcher |
O(log n) | O(1) | Yes |
TernarySearcher |
O(log₃ n) | O(1) | Yes |
FibonacciSearcher |
O(log n) | O(1) | Yes |
JumpSearcher |
O(√n) | O(1) | Yes |
Examples
Runnable examples for every algorithm are in the examples/ directory.
Documentation
Documentation
¶
Overview ¶
Package retrievium provides a collection of searching algorithm implementations behind a single interface.
Every algorithm satisfies the Searcher interface, generic over any cmp.Ordered element type. Its Search method returns the index of the target value and a boolean reporting whether it was found. BinarySearcher, TernarySearcher, FibonacciSearcher, and JumpSearcher require the input slice to be sorted in ascending order; LinearSearcher works on any input.
All searchers are stateless empty structs. The zero value of each is ready to use, and because they hold no state a single value may be shared and used concurrently by multiple goroutines.
Example ¶
Every searcher satisfies Searcher[int], so algorithms are interchangeable.
package main
import (
"fmt"
"math/rand/v2"
"slices"
"github.com/danielriddell21/retrievium/v2"
)
func sortedSlice(n int) []int {
r := rand.New(rand.NewPCG(42, 0))
s := make([]int, n)
for i := range s {
s[i] = r.IntN(10000) - 5000
}
slices.Sort(s)
return s
}
// Every searcher satisfies Searcher[int], so algorithms are interchangeable.
func main() {
searchers := []retrievium.Searcher[int]{
retrievium.BinarySearcher[int]{},
retrievium.TernarySearcher[int]{},
retrievium.FibonacciSearcher[int]{},
}
haystack := []int{1, 3, 5, 7, 9, 11}
target := 7
for _, s := range searchers {
idx, ok := s.Search(haystack, target)
fmt.Printf("%s: index %d found %v\n", s.Name(), idx, ok)
}
}
Output: Binary Search: index 3 found true Ternary Search: index 3 found true Fibonacci Search: index 3 found true
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BinarySearcher ¶
BinarySearcher searches a sorted slice using binary search, repeatedly halving the search interval. It implements the Searcher interface and requires haystack to be sorted in ascending order.
Binary search runs in O(log n) time and O(1) space.
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/retrievium/v2"
)
func main() {
s := retrievium.BinarySearcher[int]{}
fmt.Println(s.Search([]int{1, 3, 5, 7, 9}, 7))
}
Output: 3 true
func (BinarySearcher[E]) Name ¶
func (BinarySearcher[E]) Name() string
Name returns the human-readable name of the algorithm, "Binary Search".
Example ¶
ExampleBinarySearcher_Name prints the algorithm's human-readable name.
package main
import (
"fmt"
"github.com/danielriddell21/retrievium/v2"
)
func main() {
fmt.Println(retrievium.BinarySearcher[int]{}.Name())
}
Output: Binary Search
func (BinarySearcher[E]) Search ¶
func (BinarySearcher[E]) Search(haystack []E, target E) (int, bool)
Search returns the index of target in haystack and true, or 0 and false if target is not present. haystack must be sorted in ascending order; the result is unspecified otherwise.
Example ¶
ExampleBinarySearcher_Search shows that Search reports the index of a value that is present and false for one that is absent.
package main
import (
"fmt"
"github.com/danielriddell21/retrievium/v2"
)
func main() {
s := retrievium.BinarySearcher[int]{}
fmt.Println(s.Search([]int{1, 3, 5, 7, 9}, 5)) // present
fmt.Println(s.Search([]int{1, 3, 5, 7, 9}, 4)) // absent
}
Output: 2 true 0 false
type FibonacciSearcher ¶
FibonacciSearcher searches a sorted slice using Fibonacci search, dividing the search range with Fibonacci numbers instead of halving it. It implements the Searcher interface and requires haystack to be sorted in ascending order.
Avoiding division makes Fibonacci search useful when sequential memory access is costly. It runs in O(log n) time and O(1) space.
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/retrievium/v2"
)
func main() {
s := retrievium.FibonacciSearcher[int]{}
fmt.Println(s.Search([]int{1, 3, 5, 7, 9}, 7))
}
Output: 3 true
func (FibonacciSearcher[E]) Name ¶
func (FibonacciSearcher[E]) Name() string
Name returns the human-readable name of the algorithm, "Fibonacci Search".
func (FibonacciSearcher[E]) Search ¶
func (FibonacciSearcher[E]) Search(haystack []E, target E) (int, bool)
Search returns the index of target in haystack and true, or 0 and false if target is not present. haystack must be sorted in ascending order; the result is unspecified otherwise.
type JumpSearcher ¶
JumpSearcher searches a sorted slice using jump search, advancing in fixed blocks of √n elements to find the block containing the target and then scanning within it. It implements the Searcher interface and requires haystack to be sorted in ascending order.
Jump search runs in O(√n) time and O(1) space.
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/retrievium/v2"
)
func main() {
s := retrievium.JumpSearcher[int]{}
fmt.Println(s.Search([]int{1, 3, 5, 7, 9}, 7))
}
Output: 3 true
func (JumpSearcher[E]) Name ¶
func (JumpSearcher[E]) Name() string
Name returns the human-readable name of the algorithm, "Jump Search".
func (JumpSearcher[E]) Search ¶
func (JumpSearcher[E]) Search(haystack []E, target E) (int, bool)
Search returns the index of target in haystack and true, or 0 and false if target is not present. haystack must be sorted in ascending order; the result is unspecified otherwise.
type LinearSearcher ¶
LinearSearcher searches a slice using linear search, scanning every element in sequence. It implements the Searcher interface and is the only algorithm in this package that does not require haystack to be sorted.
The standard library's slices.Index does the same job; LinearSearcher exists so linear search sits alongside the other algorithms behind one interface.
Linear search runs in O(n) time and O(1) space.
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/retrievium/v2"
)
func main() {
s := retrievium.LinearSearcher[int]{}
fmt.Println(s.Search([]int{9, 3, 7, 1, 5}, 7))
}
Output: 2 true
func (LinearSearcher[E]) Name ¶
func (LinearSearcher[E]) Name() string
Name returns the human-readable name of the algorithm, "Linear Search".
func (LinearSearcher[E]) Search ¶
func (LinearSearcher[E]) Search(haystack []E, target E) (int, bool)
Search returns the index of the first occurrence of target in haystack and true, or 0 and false if target is not present. haystack need not be sorted.
type Searcher ¶
type Searcher[E cmp.Ordered] interface { // Search returns the index of target in haystack and true, or 0 and false // if target is not present. [BinarySearcher], [TernarySearcher], // [FibonacciSearcher], and [JumpSearcher] require haystack to be sorted in // ascending order. Search(haystack []E, target E) (int, bool) // Name returns the human-readable name of the algorithm. Name() string }
Searcher is the interface implemented by every searching algorithm in this package. E is the element type, which may be any cmp.Ordered type.
Implementations are stateless: the zero value is ready to use and is safe for concurrent use by multiple goroutines.
type TernarySearcher ¶
TernarySearcher searches a sorted slice using ternary search, dividing the search interval into three equal parts each iteration. It implements the Searcher interface and requires haystack to be sorted in ascending order.
Ternary search runs in O(log₃ n) time and O(1) space.
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/retrievium/v2"
)
func main() {
s := retrievium.TernarySearcher[int]{}
fmt.Println(s.Search([]int{1, 3, 5, 7, 9}, 7))
}
Output: 3 true
func (TernarySearcher[E]) Name ¶
func (TernarySearcher[E]) Name() string
Name returns the human-readable name of the algorithm, "Ternary Search".
func (TernarySearcher[E]) Search ¶
func (TernarySearcher[E]) Search(haystack []E, target E) (int, bool)
Search returns the index of target in haystack and true, or 0 and false if target is not present. haystack must be sorted in ascending order; the result is unspecified otherwise.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
examples
|
|
|
binary_version_lookup
command
Package main finds a software version in a sorted changelog using Binary Search.
|
Package main finds a software version in a sorted changelog using Binary Search. |
|
fibonacci_library_catalogue
command
Package main searches a library catalogue by call number using Fibonacci Search.
|
Package main searches a library catalogue by call number using Fibonacci Search. |
|
jump_sensor_reading
command
Package main finds a temperature reading in a sorted sensor log using Jump Search.
|
Package main finds a temperature reading in a sorted sensor log using Jump Search. |
|
linear_log_scanner
command
Package main scans an unsorted application log for error codes using Linear Search.
|
Package main scans an unsorted application log for error codes using Linear Search. |
|
ternary_salary_band
command
Package main locates a salary in a pay scale using Ternary Search.
|
Package main locates a salary in a pay scale using Ternary Search. |