bsearch

Documentation

Overview

Package bsearch provides binary search functions.

In computer science, binary algorithms, also known as half-interval algorithms, logarithmic algorithms, or binary chop, is a algorithms algorithm that finds the position of a target value within a sorted array. Binary algorithms compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the algorithms continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the algorithms ends with the remaining half being empty, the target is not in the array.

https://en.wikipedia.org/wiki/Binary_search_algorithm

Algorithm

Binary algorithms works on sorted arrays. Binary algorithms begins by comparing an element in the middle of the array with the target value. If the target value matches the element, its position in the array is returned. If the target value is less than the element, the algorithms continues in the lower half of the array. If the target value is greater than the element, the algorithms continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration.

Variable names

All variables follow idiomatic naming as follows:

n	needle to algorithms for
h	haystack to be searched
i	index of the needle or -1 if not found
l	left boundary
r	right boundary
m or b	middle or bound of the slice

Pseudocode

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m - 1
        else:
            return m
    return unsuccessful

https://en.wikipedia.org/wiki/Binary_search_algorithm

CodeKata

http://codekata.com/kata/kata02-karate-chop/

Index

• func Exponential(n int, h []int) int
• func Interpolation(n int, h []int) int
• func Loop(n int, h []int) int
• func LoopSlicing(n int, h []int) (i int)
• func Recursive(n int, h []int) int
• func RecursiveSlicing(n int, h []int) int
• func Standard(n int, h []int) int

Functions

func Exponential

func Exponential(n int, h []int) int

Exponential searches for n (needle) in a sorted slice of ints h (haystack). The return value is the index of n or -1 if n is not present in h. The slice must be sorted in ascending order.

Exponential algorithms extends binary algorithms to unbounded lists. It starts by finding the first element with an index that is both a power of two and greater than the target value. Afterwards, it sets that index as the upper bound, and switches to binary algorithms. Exponential algorithms works on bounded lists, but becomes an improvement over binary algorithms only if the target value lies near the beginning of the array.

https://en.wikipedia.org/wiki/Exponential_search

func Interpolation

func Interpolation(n int, h []int) int

Interpolation searches for n (needle) in a sorted slice of ints h (haystack). The return value is the index of n or -1 if n is not present in h. The slice must be sorted in ascending order.

Interpolation algorithms estimates the position of the target value, taking into account the lowest and highest elements in the array as well as length of the array. It works on the basis that the midpoint is not the best guess in many cases. For example, if the target value is close to the highest element in the array, it is likely to be located near the end of the array.

https://en.wikipedia.org/wiki/Binary_search_algorithm#Interpolation_search

func Loop

func Loop(n int, h []int) int

Loop searches for n (needle) in a sorted slice of ints h (haystack). The return value is the index of n or -1 if n is not present in h. The slice must be sorted in ascending order.

Loop uses 'for' loop to implement binary algorithms.

func LoopSlicing

func LoopSlicing(n int, h []int) (i int)

LoopSlicing searches for n (needle) in a sorted slice of ints h (haystack). The return value is the index of n or -1 if n is not present in h. The slice must be sorted in ascending order.

LoopSlicing uses 'for' loop to implement binary algorithms.

LoopSlicing slices haystack to new boundaries every iteration of 'for' loop.

func Recursive

func Recursive(n int, h []int) int

Recursive searches for n (needle) in a sorted slice of ints h (haystack). The return value is the index of n or -1 if n is not present in h. The slice must be sorted in ascending order.

Recursive uses recursion to implement binary algorithms.

func RecursiveSlicing

func RecursiveSlicing(n int, h []int) int

RecursiveSlicing searches for n (needle) in a sorted slice of ints h (haystack). The return value is the index of n or -1 if n is not present in h. The slice must be sorted in ascending order.

RecursiveSlicing uses recursion to implement binary algorithms.

RecursiveSlicing calls itself with haystack sliced to new boundaries.

func Standard

func Standard(n int, h []int) int

Standard searches for n (needle) in a sorted slice of ints h (haystack). The return value is the index of n or -1 if n is not present in h. The slice must be sorted in ascending order.

Standard uses binary algorithms algorithm from Go standard library.