Learning algorithms again (Part 1)

Corner stone of computer science is the Algorithms, here is what Wikipedia says about it:

Algorithm is a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

Since the school years I was learning various algorithms which was followed by the University years.

Modern developers are pretty spoiled by the variaty of available tools and frameworks that implement every major algorithm, so some might argue that it is not necessary for nowadays developers to learn algorithms hence they all (or at least most popular ones) are built into programming languages' standard libraries. But I'd argue that, because it is still important to understand the tool works internally before applying it to some problem.

Few years ago I was lucky to read book created by Robert Sedgewick and Kevin Wayne called "Algorithms" (by the time of writing this post it is already 4th edition). This book provided me with really deep and thorough explanation of all major algorithms and data structures with the step by step examples and implementations written in Java. It is a gem indeed, I'd recommend it to any developer.

But time flies and if you aren't working much with certain things you become rusty in them that sort thing. So I've decided to revamp my knowledge and read the book again. And in order to make my memories to last long I'v decided to follow every implementation of the algorithm and provide similar implementation in different language. This language is Go.

Why Go? At the moment there are Java, Scala and .NET implementations. Go is strictly typed language, it pretty simple, fast concise and I really enjoying developing things in it.

And as a result here is the first algorithm - "Binary serach" implemented in Go:

func rank(key int, a []int) int {
	lo := 0
	hi := len(a) - 1
	for lo <= hi {
		// Key is in a[lo..hi] or not present.
		mid := lo + (hi-lo)/2
		if key < a[mid] {
			hi = mid - 1
		} else if key > a[mid] {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}

func BinarySearch(name string, key int) {
	in := inout.InFromString(name)
	whitelist := in.ReadAllInts()
	sort.Ints(whitelist)

	fmt.Printf("search in sorted list: %#v\n", whitelist)

	index := rank(key, whitelist)
	if index == -1 {
		fmt.Printf("key %d not found in %s\n", key, name)
		return
	}

	fmt.Printf("key %d found at index %d\n", key, index)
}

I will be adding more and more algorithms soon in - algorithms-go project. Cheers!