binarysearch

Documentation

Overview

This code is implemented by referring to https://github.com/UWHustle/Efficiently-Searching-In-Memory-Sorted-Arrays.

Index

• func BinarySearchByKey(a []byte, sz int, compFunc func(x []byte) int) (int, int)
• func InterpolationSearchByOffset(a []byte, sz int32, offset int32) (int, int)
• func LowerBoundInt64Ascending(a []int64, x int64) int
• func LowerBoundInt64Descending(a []int64, x int64) int
• func SIPSearchByKey(a []byte, is *ISSet, sz int, x []byte, value int, compFu func(x []byte) int, ...) (int, int, int)
• func TIPSearchByKey(a []byte, ts *TSSet, sz int, value int, compFu func(x []byte) int, ...) (int, int, int)
• func UpperBoundInt64Ascending(a []int64, x int64) int
• func UpperBoundInt64Descending(a []int64, x int64) int
• type ISSet
  • func (is *ISSet) Intrpolation1(value int, mid int, sz int) int
  • func (is *ISSet) Intrpolation2(value int, sz int) int
• type TSSet
  • func (ts *TSSet) Intrpolation1(value int, x_0 int, x_1 int, x_2 int, sz int) int
  • func (ts *TSSet) Intrpolation2(value int, sz int) int

Functions

func BinarySearchByKey

func BinarySearchByKey(a []byte, sz int, compFunc func(x []byte) int) (int, int)

func InterpolationSearchByOffset

func InterpolationSearchByOffset(a []byte, sz int32, offset int32) (int, int)

func LowerBoundInt64Ascending

func LowerBoundInt64Ascending(a []int64, x int64) int

LowerBoundInt64 looks for the first element sorted in ascending order that is smaller than the target value. return the index of that element if it exists, otherwise return -1.

func LowerBoundInt64Descending

func LowerBoundInt64Descending(a []int64, x int64) int

LowerBoundInt64Descending looks for the first element sorted in descending order that is smaller than the target value. return the index of that element if it exists, otherwise return -1.

func SIPSearchByKey

func SIPSearchByKey(a []byte, is *ISSet, sz int, x []byte, value int, compFu func(x []byte) int, guard_off int) (int, int, int)

func TIPSearchByKey

func TIPSearchByKey(a []byte, ts *TSSet, sz int, value int, compFu func(x []byte) int, guard_off int) (int, int, int)

func UpperBoundInt64Ascending

func UpperBoundInt64Ascending(a []int64, x int64) int

UpperBoundInt64 looks for the first element sorted in ascending order that is greater than or equal to the target value. return the index of that element if it exists, otherwise return -1.

func UpperBoundInt64Descending

func UpperBoundInt64Descending(a []int64, x int64) int

LowerBoundInt64Descending looks for the first element sorted in descending order that is greater than or equal to the target value. return the index of that element if it exists, otherwise return -1.

Types

type ISSet

type ISSet struct {
	A             *[]byte
	Slope         float64
	F_aL          float64
	F_width_range float64
}

func (*ISSet) Intrpolation1

func (is *ISSet) Intrpolation1(value int, mid int, sz int) int

func (*ISSet) Intrpolation2

func (is *ISSet) Intrpolation2(value int, sz int) int

type TSSet

type TSSet struct {
	A *[]byte
	// contains filtered or unexported fields
}

func (*TSSet) Intrpolation1

func (ts *TSSet) Intrpolation1(value int, x_0 int, x_1 int, x_2 int, sz int) int

func (*TSSet) Intrpolation2

func (ts *TSSet) Intrpolation2(value int, sz int) int