The highest tagged major version is
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.
Installation
go get github.com/danielriddell21/retrievium@latest
Quick start
import "github.com/danielriddell21/retrievium"
s := retrievium.BinarySearcher{}
idx := s.Search([]int{1, 3, 5, 7, 9}, 7)
// idx == 3
fmt.Println(s.Name()) // "Binary Search"
Every searcher satisfies the Searcher interface:
type Searcher interface {
Search(haystack []int, target int) int
Name() string
}
Search returns the index of the target, or -1 if not present.
BinarySearcher, TernarySearcher, FibonacciSearcher, and JumpSearcher require the input to be sorted in ascending order. LinearSearcher works on any input.
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.
Docs
Documentation
¶
Overview ¶
Package retrievium provides a collection of searching algorithm implementations behind a single interface.
Every algorithm satisfies the Searcher interface. Its Search method operates on a slice of integers and returns the index of the target value, or -1 if it is not 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 the Searcher interface, so algorithms are interchangeable.
package main
import (
"fmt"
"math/rand/v2"
"sort"
"github.com/danielriddell21/retrievium"
)
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
}
sort.Ints(s)
return s
}
// Every searcher satisfies the Searcher interface, so algorithms are interchangeable.
func main() {
searchers := []retrievium.Searcher{
retrievium.BinarySearcher{},
retrievium.TernarySearcher{},
retrievium.FibonacciSearcher{},
}
haystack := []int{1, 3, 5, 7, 9, 11}
target := 7
for _, s := range searchers {
fmt.Printf("%s: index %d\n", s.Name(), s.Search(haystack, target))
}
}
Output: Binary Search: index 3 Ternary Search: index 3 Fibonacci Search: index 3
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BinarySearcher ¶
type BinarySearcher struct{}
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"
)
func main() {
s := retrievium.BinarySearcher{}
fmt.Println(s.Search([]int{1, 3, 5, 7, 9}, 7))
}
Output: 3
func (BinarySearcher) Name ¶
func (BinarySearcher) 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"
)
func main() {
fmt.Println(retrievium.BinarySearcher{}.Name())
}
Output: Binary Search
func (BinarySearcher) Search ¶
func (BinarySearcher) Search(haystack []int, target int) int
Search returns the index of target in haystack, or -1 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 -1 for one that is absent.
package main
import (
"fmt"
"github.com/danielriddell21/retrievium"
)
func main() {
s := retrievium.BinarySearcher{}
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 -1
type FibonacciSearcher ¶
type FibonacciSearcher struct{}
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"
)
func main() {
s := retrievium.FibonacciSearcher{}
fmt.Println(s.Search([]int{1, 3, 5, 7, 9}, 7))
}
Output: 3
func (FibonacciSearcher) Name ¶
func (FibonacciSearcher) Name() string
Name returns the human-readable name of the algorithm, "Fibonacci Search".
type JumpSearcher ¶
type JumpSearcher struct{}
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"
)
func main() {
s := retrievium.JumpSearcher{}
fmt.Println(s.Search([]int{1, 3, 5, 7, 9}, 7))
}
Output: 3
func (JumpSearcher) Name ¶
func (JumpSearcher) Name() string
Name returns the human-readable name of the algorithm, "Jump Search".
type LinearSearcher ¶
type LinearSearcher struct{}
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.
Linear search runs in O(n) time and O(1) space.
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/retrievium"
)
func main() {
s := retrievium.LinearSearcher{}
fmt.Println(s.Search([]int{9, 3, 7, 1, 5}, 7))
}
Output: 2
func (LinearSearcher) Name ¶
func (LinearSearcher) Name() string
Name returns the human-readable name of the algorithm, "Linear Search".
type Searcher ¶
type Searcher interface {
// Search returns the index of target in haystack, or -1 if target is not
// present. [BinarySearcher], [TernarySearcher], [FibonacciSearcher], and
// [JumpSearcher] require haystack to be sorted in ascending order.
Search(haystack []int, target int) int
// Name returns the human-readable name of the algorithm.
Name() string
}
Searcher is the interface implemented by every searching algorithm in this package.
Implementations are stateless: the zero value is ready to use and is safe for concurrent use by multiple goroutines.
type TernarySearcher ¶
type TernarySearcher struct{}
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"
)
func main() {
s := retrievium.TernarySearcher{}
fmt.Println(s.Search([]int{1, 3, 5, 7, 9}, 7))
}
Output: 3
func (TernarySearcher) Name ¶
func (TernarySearcher) Name() string
Name returns the human-readable name of the algorithm, "Ternary Search".
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. |