search

Documentation

Overview

Package search includes various algorithms for searching.

Index

• func Binary[E cmp.Ordered](x []E, target E) int
• func BinaryCmp[T any](x []T, target T, cmp func(x, y T) int) int
• func BinaryPredicate[T any](x []T, p func(T) bool) int

Functions

func Binary

func Binary[E cmp.Ordered](x []E, target E) int

BinaryCmp implements binary search. It returns the index of the target in the slice if present. If the target is not found, it returns the index where the target should be inserted. The returned index is in the interval [0, len(x)]. If the slice contains multiple elements with the specified value, there is no guarantee which one will be found. The slice must be sorted in increasing order.

func BinaryCmp

func BinaryCmp[T any](x []T, target T, cmp func(x, y T) int) int

BinaryCmp implements binary search. It returns the index of the target in the slice if present. If the target is not found, it returns the index where the target should be inserted. The returned index is in the interval [0, len(x)]. If the slice contains multiple elements with the specified value, there is no guarantee which one will be found. The slice must be sorted in increasing order, defined by the comparison function cmp.

func BinaryPredicate

func BinaryPredicate[T any](x []T, p func(T) bool) int

BinaryPredicate implements binary search. It returns the smallest index i in the slice x at which p(x[i]) is true, assuming that, p(x[i]) == true implies p(x[i+1]) == true. That is, BinaryPredicate requires that p is false for some (possibly empty) prefix of the slice and then true for the (possibly empty) remainder. If there is no such index i, BinaryPredicate returns i = n.