search

Documentation

Overview

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

Index

• func Binary(array []int, target int, lowIndex int, highIndex int) int
• func BinaryIterative(array []int, target int, lowIndex int, highIndex int) int
• func Interpolation(sortedData []int, guess int) int
• func Linear(array []int, query int) int

Functions

func Binary

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

Binary Binary Search

func BinaryIterative

func BinaryIterative(array []int, target int, lowIndex int, highIndex int) int

BinaryIterative Iterative Binary Search

func Interpolation

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

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 Linear

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

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