searchalgorithms

Documentation

Overview

Package searchalgorithms implements many of the most used search algorithms using the Go programming language.

It utilizes the latest and most efficient techniques, like generics, in order to make functions work for as many types as possible.

Functions typically take in a slice of values and a value to search for. They typically return the index of the (first occurrence, where applicable, of the) value and an error (if any) that occurred.

`NB`: An error is not returned if value is not found, rather the index returned is `NotFound` which is -1. An error is only returned when the log file could not be created, opened, or written to.

Index

• Constants
• func BinarySearch[T constraints.Ordered](slice []T, value T) (int, error)
• func ExponentialSearch[T constraints.Ordered](slice []T, value T) (int, error)
• func InterpolationSearch(slice []int, value int) (int, error)
• func JumpSearch[T constraints.Ordered](slice []T, value T) (int, error)
• func LinearSearch[T comparable](slice []T, value T) (int, error)

Constants

const NotFound = -1

NotFound is a constant for the return value of the search algorithm

Functions

func BinarySearch

func BinarySearch[T constraints.Ordered](slice []T, value T) (int, error)

BinarySearch finds the index of the value in the slice.

It takes in an Ordered slice and a value to find and returns the index of the value or “NotFound“ if the value is not found in the slice.

`NB`: It doesn't return the first occurrence of the value. If this is what you want, consider using `ExponentialSearch` which is an optimization of BinarySearch.

func ExponentialSearch

func ExponentialSearch[T constraints.Ordered](slice []T, value T) (int, error)

ExponentialSearch increases exponentially with each iteration until it finds a block where the target value can be found. It then performs a binary search on that block to find the target value.

The function takes in a slice of any Ordered type and a target value. It returns the index of the first occurrence of the target value or NotFound if target is not found, and error (if any).

func InterpolationSearch

func InterpolationSearch(slice []int, value int) (int, error)

InterpolationSearch is a search algorithm that finds a value in a sorted slice of values.

It takes a sorted slice of integers and the value to search for and returns the index of the first occurence of the value in the slice or “NotFound“ if the value is not found.

func JumpSearch

func JumpSearch[T constraints.Ordered](slice []T, value T) (int, error)

JumpSearch uses jump search algorithm to find a value in a sorted slice.

It takes in an Ordered sorted slice and a value and returns the index of the value and any errors.

func LinearSearch

func LinearSearch[T comparable](slice []T, value T) (int, error)

LinearSearch finds the index of a value in a slice. It operates on comparable data types i.e. int, string, float64, etc.

It takes in a slice and a value and returns the index of the first occurence of the value if it is found, otherwise it returns “NotFound“.