DEV Community

Cover image for Searching Algorithms in Go
Adnan Babakan (he/him)
Adnan Babakan (he/him)

Posted on • Updated on

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

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
}


Enter fullscreen mode Exit fullscreen mode

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))
}


Enter fullscreen mode Exit fullscreen mode

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))
}


Enter fullscreen mode Exit fullscreen mode

I will complete this list by time.

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

Top comments (1)

Collapse
 
munkhbats profile image
Munkhbat • Edited

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" )
    }
}
Enter fullscreen mode Exit fullscreen mode