J. R. Swab

How To Search A Sorted Matrix With Go

Categories: [Technology]
Tags: [programming], [golang], [algorithms]

I started learning common algorithms to better my programming ability. It’s the biggest skill set that I lack at the moment. So many problems have a common ground is these algorithms and having a good handle on them can only make problem solving easier.

I’ll post the algorithms on the blog as I get comfortable with them and share what I learned. I’m no expert so if you know a better (more clear or efficient) way of writing these algorithms please message me on any social media platform.

Since Go (Golang) is my favorite programming language I’ll use that for these walk throughs. If you don’t know Go but have programming experience, you should be able to follow along. Otherwise, it would be helpful to learn the syntax of Go to make the following code more clear.

Also, I assume you have a basic understanding of programming terminology. It would take much too long to define every word needed to explain the process. If you don’t know a word look it up.

Here is the link to the Go Playground.

Breaking Down The Code:

Our focus is in the "findNum" function starting on line twenty-one. This function takes in an integer and assigns it to the variable "num". And a slice of slices of integers "[][]int". 

(Slices operate like arrays but without a pre-defined or fixed length.)

Upon completion it returns a slice that contains the "row/column" index. If the number being searched for is not present we default to returning "-1, -1" as seen on line 37.

To avoid a nested loop, we set two variables, in this example they are "row" and "col". "Row" starts at 0, since we want to start our search in the first sub-slice. We assign the "col" variable to the length of the data held at index zero of the matrix minus one. The reason is that we want to know how many elements are in the first row and to start at the last index.

We start at the last index of the first row to allow us to move through the matrix with the question, "is num greater than the integer at 'col'". We can do this because the matrix we have is sorted like we see below.

Row 0: [ 0,  2,  4]
Row 1: [ 1,  3,  5]
Row 2: [ 6,  8, 10]
Row 3: [ 7,  9, 11]
Row 4: [12, 13, 14]

Now we get to the loop where we step through the matrix in a specific order. On line twenty-one we set the condition where the loop will execute. We want to continue to ask the questions inside the loop as long as the integer in the "row" variable is less than the total rows (or the length of the matrix slice). But we also need to make sure that the "col" variable does not run into the negative numbers or else we will be outside the range of the slice. The result is what we see at line twenty-one; "row < len(matrix) && col >= 0".

When both those conditions return true, the loop continues to the next line where we check if the number we are looking for matches the number at the current index.

num == matrix[row][col]

If it does, then we return the "row" and "col" as its own slice and the for loop ends.

When "num" is not equal to the current index, we ask one of two questions. These can be in any order; the way I set up the checks is to start with the column.

Line twenty-eight asks, “is 'num' less than the digit at the current index?”

if num < matrix[row][col]

If so, we decrease the column by one since every other number in that column will be larger than num because this is a sorted matrix.

Then we repeat and ask the loop’s main question again.

If "num" is bigger, then we increase "row" but keep the column index the same and repeat the loop.

else if num > matrix[row][col]

If both these questions are false, we can conclude that the number is not in the sorted matrix so we break out of the loop. Once we break out the program hit line thirty-seven and returns the values "-1, -1".

The Code:

// Search A Sorted Matrix
//   Coder: Jaron Swab
//   twitter.com/jrswab

package main

import "fmt"

func main() {
    matrix := [][]int{
        {0, 2, 4},
        {1, 3, 5},
        {6, 8, 10},
        {7, 9, 11},
        {12, 13, 14},
    }
    isFound := findNum(8, matrix)
    fmt.Printf("%v", isFound)
}

func findNum(num int, matrix [][]int) []int {
    row, col := 0, len(matrix[0])-1

    for row < len(matrix) && col >= 0 {
        if num == matrix[row][col] {
            return []int{row, col}
        }
        if num < matrix[row][col] {
            col--
        } else if num > matrix[row][col] {
            row++
        } else {
            break
        }
    }
    // if number does not exist in the matrix
    return []int{-1, -1}
}