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.
All implementations satisfy the Searcher interface. Search operates on a slice of integers and returns the index of the target value, or -1 if not found. BinarySearcher, TernarySearcher, FibonacciSearcher, and JumpSearcher require the input slice to be sorted in ascending order. LinearSearcher works on any input.
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 implements Binary Search. Repeatedly halves the search interval, discarding the half that cannot contain the target. Requires the input slice to be sorted in ascending order. Time: O(log n) Space: O(1)
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
type FibonacciSearcher ¶
type FibonacciSearcher struct{}
FibonacciSearcher implements Fibonacci Search. Uses Fibonacci numbers to divide the search range, avoiding division and working well when sequential memory access is costly. Requires the input slice to be sorted in ascending order. Time: O(log n) Space: O(1)
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
type JumpSearcher ¶
type JumpSearcher struct{}
JumpSearcher implements Jump Search. Jumps ahead by √n steps to find the block containing the target, then performs a linear scan within that block. Requires the input slice to be sorted in ascending order. Time: O(√n) Space: O(1)
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
type LinearSearcher ¶
type LinearSearcher struct{}
LinearSearcher implements Linear Search. Scans every element in sequence until the target is found or the slice is exhausted. Works on unsorted input. Time: O(n) Space: O(1)
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
type Searcher ¶
type Searcher interface {
// Search returns the index of target in haystack, or -1 if 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 implemented by every searching algorithm in this package.
type TernarySearcher ¶
type TernarySearcher struct{}
TernarySearcher implements Ternary Search. Divides the search interval into three equal parts each iteration, discarding the two-thirds that cannot contain the target. Requires the input slice to be sorted in ascending order. Time: O(log₃ n) Space: O(1)
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
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. |