Documentation ¶
Overview ¶
Package advsearch searches elements in sorted slices or user defined collections of any kind Because of the generic interfaces, advsearch can also be used to define possible insertion positions in a data structure or a position in a data structure based on other criteria based on the user's implementation of the Match() function.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BinarySearch ¶
func BinarySearch(s Searchable, e interface{}) (int, error)
BinarySearch searches a match of the element e in the sorted data structure s. It will return the index/position in s based on your implementation of s.Match(). Assuming that all methods of the interface Searchable run in O(1), BinarySearch will have a guaranteed time complexity of θ(log(n)) worst and average case. Pre-condition: s must be sorted!
Example ¶
package main import ( "fmt" "github.com/MauriceGit/advsearch" ) type IntSlice []int // Len is part of Searchable. func (s *IntSlice) Len() int { return len(s) } // Smaller is part of the Searchable interface func (s *IntSlice) Smaller(e interface{}, i int) bool { return e.(int) < (*s)[i] } // Match is part of the Searchable interface func (s *IntSlice) Match(e interface{}, i int) bool { return e.(int) == (*s)[i] } // GetValue is part of the SearchableInterpolation interface func (s *IntSlice) GetValue(i int) float64 { return float64((*s)[i]) } // ExtractValue is part of the SearchableInterpolation interface func (s *IntSlice) ExtractValue(e interface{}) float64 { return float64(e.(int)) } func main() { s := IntSlice{1, 2, 3, 4, 5, 6} // sorted ascending index, _ := advsearch.BinarySearch(&s, 4) fmt.Println(index) }
Output: 3
func InterpolationSearch ¶
func InterpolationSearch(s SearchableInterpolation, e interface{}) (int, error)
InterpolationSearch searches a match of the element e in the sorted data structure s. It will return the index/position in s based on your implementation of s.Match(). Assuming that all methods of the interface Searchable and SearchableInterpolation run in O(1), InterpolationSearch will have a time complexity of θ(n) worst case and θ(log(log(n))) average case. Pre-condition: s must be sorted!
Example ¶
package main import ( "fmt" "github.com/MauriceGit/advsearch" ) type IntSlice []int // Len is part of Searchable. func (s *IntSlice) Len() int { return len(s) } // Smaller is part of the Searchable interface func (s *IntSlice) Smaller(e interface{}, i int) bool { return e.(int) < (*s)[i] } // Match is part of the Searchable interface func (s *IntSlice) Match(e interface{}, i int) bool { return e.(int) == (*s)[i] } // GetValue is part of the SearchableInterpolation interface func (s *IntSlice) GetValue(i int) float64 { return float64((*s)[i]) } // ExtractValue is part of the SearchableInterpolation interface func (s *IntSlice) ExtractValue(e interface{}) float64 { return float64(e.(int)) } func main() {
Output: 3
func QuadraticBinarySearch ¶
func QuadraticBinarySearch(s SearchableInterpolation, e interface{}) (int, error)
QuadraticBinarySearch searches a match of the element e in the sorted data structure s. It will return the index/position in s based on your implementation of s.Match(). Assuming that all methods of the interface Searchable and SearchableInterpolation run in O(1), QuadraticBinarySearch will have a time complexity of θ(sqrt(n)) worst case and θ(log(log(n))) average case. Pre-condition: s must be sorted!
Example ¶
package main import ( "fmt" "github.com/MauriceGit/advsearch" ) type IntSlice []int // Len is part of Searchable. func (s *IntSlice) Len() int { return len(s) } // Smaller is part of the Searchable interface func (s *IntSlice) Smaller(e interface{}, i int) bool { return e.(int) < (*s)[i] } // Match is part of the Searchable interface func (s *IntSlice) Match(e interface{}, i int) bool { return e.(int) == (*s)[i] } // GetValue is part of the SearchableInterpolation interface func (s *IntSlice) GetValue(i int) float64 { return float64((*s)[i]) } // ExtractValue is part of the SearchableInterpolation interface func (s *IntSlice) ExtractValue(e interface{}) float64 { return float64(e.(int)) } func main() { s := IntSlice{1, 2, 3, 4, 5, 6} // sorted ascending index, _ := advsearch.QuadraticBinarySearch(&s, 4) fmt.Println(index) }
Output: 3
Types ¶
type Searchable ¶
type Searchable interface { // True, if the value of e is smaller than the element at index i Smaller(e interface{}, i int) bool // Length of the data structure (element count) Len() int // Defines if we have a match based on the index i. // Most likely when e and value at i are equal. // You may also look at the elements before or after i to // determine a match (i.e. to find a possible insertion position). Match(e interface{}, i int) bool }
Searchable is the interface to implement to be able to use BinarySearch on your data structure. The package requires that elements can be enumerated with an integer based index.
type SearchableInterpolation ¶
type SearchableInterpolation interface { // We need all defined methods from Searchable Searchable // Method to get a value that can be used to interpolate the approximate // position in your data structure. Integers or other numbers can just // be casted to float64. This will not affect your search negatively. // This is needed for interpolation search and quadratic binary search. GetValue(i int) float64 // Additionally, we don't know, what elements are in the data structure. // So we need the additional conversion function to work with e. ExtractValue(e interface{}) float64 }
SearchableInterpolation is the interface to implement to be able to use Interpolation Search and Quadratic Binary Search on your data structure.