Matrix Binary Search

matrix_binary_search.go

package main

import (
	"errors"
	"fmt"
	"os"
)

func main() {
	// CHANGE THIS VALUE TO TEST
	searchValue := 45

	matrix := fillArray()
	fmt.Println("input array:")
	printMatrix(matrix)

	x, y, err := find(matrix, searchValue)
	if err != nil {
		fmt.Println(err.Error())
		os.Exit(0)
	}

	fmt.Printf("\nfound value: %d in position: matrix[%d][%d]", matrix[x][y], x, y)
}

// find will search the key value in the matrix using binary search in
// O(log(n))
func find(matrix *[9][9]int, key int) (x int, y int, err error) {
	columnLength, rowLength := len(matrix), len(matrix[0])
	var low, mid int
	high := columnLength * rowLength

	for low < high {
		mid = (low + high) / 2
		if matrix[mid/columnLength][mid%columnLength] == key {
			return mid / columnLength, mid % columnLength, nil
		} else if matrix[mid/columnLength][mid%columnLength] < key {
			high = mid
		} else {
			low = mid
		}
	}
	return 0, 0, errors.New("the number doesn't exist")
}

// fillArray function will generate a testing array and it's
// doing it in O(n^2). As this is only used to setup, we are
// not optimizing it.
func fillArray() *[9][9]int {
	var matrix [9][9]int
	var counter int
	for i := 8; i >= 0; i-- {
		for j := 8; j >= 0; j-- {
			matrix[i][j] = counter
			counter++
		}
	}
	return &matrix
}

// printMatrix will print the matrix in a
// visual way.
func printMatrix(matrix *[9][9]int) {
	for i := 0; i <= 8; i++ {
		fmt.Println(matrix[i][:])
	}
}