Documentation
¶
Overview ¶
Package sequence provides search algorithms on sequences.
For better performance, all functions in this package are unsafe for concurrency unless otherwise specified.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BinarySearch ¶
func BinarySearch[Item any](itf BinarySearchInterface[Item], goal Item) int
BinarySearch finds goal in itf using binary search algorithm, and returns its index.
itf must be sorted in ascending order! (If itf is in descending order, you can change the behavior of your itf.Compare such that it returns +1 if the item is less than the search goal, and returns -1 if the item is greater than the search goal.) This function won't check whether itf is sorted. You must sort itf before calling this function, otherwise, goal may not be found as expected.
If itf.Compare returns (0, true) for multiple items, it returns the index of one of them.
It returns -1 if goal is not found.
goal is only used to call the method SetGoal of itf. It's OK to handle goal in your implementation of BinarySearchInterface, and set goal to an arbitrary value, such as a zero value.
Time complexity: O(log n + m), where n = itf.Len(), m is the number of items that let itf.Compare return (0, false).
func BinarySearchMaxLess ¶
func BinarySearchMaxLess[Item any]( itf BinarySearchInterface[Item], goal Item, ) int
BinarySearchMaxLess finds the maximum item less than goal in itf using binary search algorithm, and returns its index.
itf must be sorted in ascending order! (If itf is in descending order, you can change the behavior of your itf.Compare such that it returns +1 if the item is less than the search goal, and returns -1 if the item is greater than the search goal, and then use function BinarySearchMinGreater instead of this function.) This function won't check whether itf is sorted. You must sort itf before calling this function, otherwise, the item may not be found as expected.
If multiple items satisfy the condition, it returns the index of the last one of them.
It returns -1 if there is no such item in itf.
goal is only used to call the method SetGoal of itf. It's OK to handle goal in your implementation of BinarySearchInterface, and set goal to an arbitrary value, such as a zero value.
Time complexity: O(log n), where n = itf.Len().
func BinarySearchMinGreater ¶
func BinarySearchMinGreater[Item any]( itf BinarySearchInterface[Item], goal Item, ) int
BinarySearchMinGreater finds the minimum item greater than goal in itf using binary search algorithm, and returns its index.
itf must be sorted in ascending order! (If itf is in descending order, you can change the behavior of your itf.Compare such that it returns +1 if the item is less than the search goal, and returns -1 if the item is greater than the search goal, and then use function BinarySearchMaxLess instead of this function.) This function won't check whether itf is sorted. You must sort itf before calling this function, otherwise, the item may not be found as expected.
If multiple items satisfy the condition, it returns the index of the first one of them.
It returns -1 if there is no such item in itf.
goal is only used to call the method SetGoal of itf. It's OK to handle goal in your implementation of BinarySearchInterface, and set goal to an arbitrary value, such as a zero value.
Time complexity: O(log n), where n = itf.Len().
Types ¶
type BinarySearchInterface ¶
type BinarySearchInterface[Item any] interface { // SetGoal sets the search goal. // // It will be called once at the beginning of the search functions. // // Its implementation can do initialization for each search in this method. SetGoal(goal Item) // Len returns the number of items in the sequence. Len() int // Compare compares the item with index i and the search goal. // // It returns an integer and a boolean indicator, // where the integer represents the item with index i is less than, // equal to, or greater than the search goal, // and the indicator reports whether the item with index i // is the search goal (only valid when the returned integer is 0). // // The returned integer is // // -1 if the item with index i is less than the search goal, // 0 if the item with index i is equal to the search goal, // +1 if the item with index i is greater than the search goal. // // It panics if i is out of range. Compare(i int) (lessEqualOrGreater int, isGoal bool) }
BinarySearchInterface represents an integer-indexed sequence used in the binary search algorithm.
Its type parameter Item represents the type of item in the sequence.
func WrapArrayLessEqual ¶ added in v0.5.0
func WrapArrayLessEqual[Item any]( data array.Array[Item], lessFn compare.LessFunc[Item], equalFn compare.EqualFunc[Item], ) BinarySearchInterface[Item]
WrapArrayLessEqual wraps github.com/donyori/gogo/container/sequence/array.Array with github.com/donyori/gogo/function/compare.LessFunc and github.com/donyori/gogo/function/compare.EqualFunc to a BinarySearchInterface.
data is the array in which to search.
lessFn is used to compare items in data with the search goal. It cannot be nil. If both lessFn(item, goal) and lessFn(goal, item) return false, item and goal are considered equal, and the first return value of method Compare is 0.
lessFn must describe a strict weak ordering. See <https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings> for details.
Note that floating-point comparison (the < operator on float32 or float64 values) is not a strict weak ordering when not-a-number (NaN) values are involved.
WrapArrayLessEqual panics if lessFn is nil.
equalFn is an additional function to test whether an item is the search goal. If equalFn is nil, the item is considered the search goal when they are equal. equalFn will be called only when both lessFn(item, goal) and lessFn(goal, item) return false. When equalFn is non-nil, the second return value of method Compare is true if and only if lessFn(item, goal) returns false, lessFn(goal, item) returns false, and equalFn(item, goal) returns true.
Source Files