Searching Algorithms in Go

Hey, Dev.to community!

In this post, I am sharing with you the Go code I've written for some famous searching algorithms.

Table of Contents

• Linear Search
• Binary Search
• Jump Search

Linear Search

Linear search is the most basic search algorithm. What you'd do in this algorithm is basically iterate through an array until you find the desired result and return its index.

package main

import "fmt"

func linearSort(arr []int, s int) int {
    for i, v := range arr {
        if s == v {
            return i
        }
    }

    return -1
}

func main() {
    var n = []int{9, 1, 33, 21, 78, 42, 4}

    fmt.Println(linearSort(n, 78)) // 4
}

Binary Search

Binary search is a famous and fast searching algorithm. This algorithm requires you to provide it with an already ascendingly sorted array. This sort basically examines the middle value of the array to find out if it is equal to our target or not. If the middle value is less than the target it means the target is beyond the middle value, and if it is larger it means the target is before the middle value. And the algorithm tends to find the middle value until it matches the target.

To understand this algorithm better you can watch the video below:

package main

import "fmt"

func binarySearch(arr []int, s int) int {
    var leftPointer = 0
    var rightPointer = len(arr) - 1
    for leftPointer <= rightPointer {
        var midPointer = int((leftPointer + rightPointer) / 2)
        var midValue = arr[midPointer]

        if midValue == s {
            return midPointer
        } else if midValue < s {
            leftPointer = midPointer + 1
        } else {
            rightPointer = midPointer - 1
        }
    }

    return -1
}

func main() {
    var n = []int{2, 9, 11, 21, 22, 32, 36, 48, 76}

    fmt.Println(binarySearch(n, 32))
}

Jump Search

Jump search is an algorithm used for sorted arrays. You are going to jump by the square root of the length of the array until you find a value larger than or equal to the target. Then you have to implement a reverse linear search to determine the final result.

To understand this algorithm better you can watch the video below:

package main

import (
    "fmt"
    "math"
)

func jumpSearch(arr []int, s int) int {

    var blockSize = int(math.Sqrt(float64(len(arr))))

    var i = 0
    for {

        if arr[i] >= s {
            break
        }

        if i > len(arr) {
            break
        }

        i += blockSize
    }

    for j := i; j > 0; j-- {
        if arr[j] == s {
            return j
        }
    }

    return -1
}

func main() {
    var n = []int{2, 9, 11, 21, 22, 32, 36, 48, 76, 90}

    fmt.Println(jumpSearch(n, 76))
}

---

I will complete this list by time.

BTW! Check out my free Node.js Essentials E-book here:

NodeJS Essentials | Free E-Book

Adnan Babakan (he/him) ・ Sep 11 '20

#node #javascript #books

Comments

[Munkhbat]

This could be a lot faster for Binary search.

package main

import "fmt"

func binarySearch(arr []int, s int, index int) (int, bool) {
    var leftPointer = 0
    var ret int
    var found bool
    var rightPointer = len(arr) - 1
    if leftPointer != rightPointer {
        var midPointer = int((leftPointer + rightPointer) / 2)
        var midValue = arr[midPointer]

        if midValue == s {
            ret = midPointer + index
            found = true
        } else if midValue < s {
            ret, found = binarySearch(arr[midPointer:rightPointer], s, midPointer)
        } else {
            ret, found = binarySearch(arr[leftPointer:midPointer], s, index)
        }

        if found == false {
            return -1, false
        }
    }

    return ret, true
}

func main() {
    var n = []int{2, 9, 11, 21, 22, 32, 36, 48, 76}
    ret, found := binarySearch(n, 32, 0)

    if found == true {
        fmt.Println("Found : ", n[ret])
    }else{
        fmt.Println("Not found" )
    }
}