search

Documentation

Overview

Package search is a subpackage dedicated to all searching algorithms related to slices/arrays.

Index

• Variables
• func Binary(array []int, target int, lowIndex int, highIndex int) (int, error)
• func BinaryIterative(array []int, target int) (int, error)
• func Interpolation(sortedData []int, guess int) (int, error)
• func Jump(array []int, target int) (int, error)
• func Jump2(arr []int, target int) (int, error)
• func Linear(array []int, query int) (int, error)
• func LowerBound(array []int, target int) (int, error)
• func SelectK(array []int, k int) (int, error)
• func TernaryMax(a, b, epsilon float64, f func(x float64) float64) (float64, error)
• func TernaryMin(a, b, epsilon float64, f func(x float64) float64) (float64, error)
• func UpperBound(array []int, target int) (int, error)

Variables

var ErrNotFound = errors.New("target not found in array")

ErrNotFound is returned by search functions when target is not found

Functions

func Binary

func Binary(array []int, target int, lowIndex int, highIndex int) (int, error)

Binary search for target within a sorted array by repeatedly dividing the array in half and comparing the midpoint with the target. This function uses recursive call to itself. If a target is found, the index of the target is returned. Else the function return -1 and ErrNotFound.

func BinaryIterative

func BinaryIterative(array []int, target int) (int, error)

BinaryIterative search for target within a sorted array by repeatedly dividing the array in half and comparing the midpoint with the target. Unlike Binary, this function uses iterative method and not recursive. If a target is found, the index of the target is returned. Else the function return -1 and ErrNotFound.

func Interpolation

func Interpolation(sortedData []int, guess int) (int, error)

Interpolation searches for the entity in the given sortedData. if the entity is present, it will return the index of the entity, if not -1 will be returned. see: https://en.wikipedia.org/wiki/Interpolation_search Complexity

Worst: O(N)
Average: O(log(log(N))  if the elements are uniformly distributed
Best: O(1)

Example

fmt.Println(InterpolationSearch([]int{1, 2, 9, 20, 31, 45, 63, 70, 100},100))

func Jump

func Jump(array []int, target int) (int, error)

Jump search works by jumping multiple steps ahead in sorted list until it find an item larger than target, then create a sublist of item from the last searched item up to the current item and perform a linear search.

func Jump2

func Jump2(arr []int, target int) (int, error)

func Linear

func Linear(array []int, query int) (int, error)

Linear Simple linear search algorithm that iterates over all elements of an array in the worst case scenario

func LowerBound

func LowerBound(array []int, target int) (int, error)

Returns index to the first element in the range [0, len(array)-1] that is not less than (i.e. greater or equal to) target. return -1 and ErrNotFound if no such element is found.

func SelectK

func SelectK(array []int, k int) (int, error)

func TernaryMax

func TernaryMax(a, b, epsilon float64, f func(x float64) float64) (float64, error)

TernaryMax is a function to search for maximum value of a uni-modal function `f` in the interval [a, b]. a and b should be finit numbers

func TernaryMin

func TernaryMin(a, b, epsilon float64, f func(x float64) float64) (float64, error)

TernaryMin is a function to search for minimum value of a uni-modal function `f` in the interval [a, b]. a and b should be finit numbers.

func UpperBound

func UpperBound(array []int, target int) (int, error)

Returns index to the first element in the range [lowIndex, len(array)-1] that is greater than target. return -1 and ErrNotFound if no such element is found.