Algorithms in Golang

Algorithms and data structure is a big portion of our code, and starting out you might come across Binary Search as one of your lessons, If you are into Go, consider this code, as it helps you solve this common question.

Calculating mid in binary search

Most cases when you write a binary search you make the mistake of using (low + high )/ 2 and while this is valid for uint, unsigned integers (0, 255), you may in certain cases, run to a integers (-128, 127) where you run to some weird issues, this code will demonstrate that for you

func main() {

    var low int8 = 80
    var high int8 = 120
    var mid int8

    mid = (low + (high-low)/2)
    fmt.Println(mid)
    mid = (high + low) / 2
    fmt.Println(mid)
}

Console prints out:

100

-28

try it out

If you need more informations, No one is better than Joshua Bloch article, at Google blog

Binary Search in Golang and Linear Search method

package main

import "fmt"

func main() {
    b := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 100, 159, 192, 350, 1230, 1341, 4533}

    fmt.Println(BinarySearch(b, 31))
    fmt.Println(LinearSearch(b, 31))

}

func BinarySearch(haystack []int, needle int) bool {
    var high, low, mid, val int
    low = 0
    high = len(haystack)
    for low < high {
        mid = (low + ((high - low) / 2))
        val = haystack[mid]
        fmt.Println(val)
        if val == needle {
            return true
        } else if val > needle {
            high = mid
        } else if val < needle {
            low = mid + 1
        }
    }
    return false
}

func LinearSearch(haystack []int, needle int) bool {
    for _, v := range haystack {
        fmt.Println(v)
        if v == needle {
            return true
        }
    }
    return false
}