Golang: Jump search algorithm (jump your Go skills)

Golang: Jump search algorithm (jump your Go skills)

This jump search technique will serve your carrier, take a minute to jump your carrier as well.

Search algorithms

Whenever you search an element in an array, you have bunch of choices to reduce the time space and memory space, this optimizations add up, and its referred to as a technology, like if you have some extra RAM storage.

One common technique you might use, is the jump search Where you search, each foot equals the root of number of elements, so in an array of 100 your jump is 10, in an array of 10000 the jump is 100. Then once you have crossed the desired value, you go back between the last step and this one. And iterate though a much smaller array.


func TwoCrystalBalls(array []int, target int) int {
    step := int(math.Round(math.Sqrt(float64(len(array)))))
    rbound := len(array)
    for i := step; i < len(array); i += step {
        if array[i] > target {
            rbound = i
            break
        }
    }

    for i := rbound - step; i < rbound; i++ {
        if array[i] == target {
            return array[i]
        }
        if array[i] > target {
            break
        }
    }
    return -1
}

func JumpBinarySearch(array []int, target int) int {
    step := int(math.Round(math.Sqrt(float64(len(array)))))
    var high int
    for i := step; i < len(array); i += step {
        if array[i] > target {
            high = i
            break
        }
    }
    low := high - step
    for low < high {
        mid := low + ((high - low) / 2)
        val := array[mid]
        if val == target {
            return val
        } else if val < target {
            low = mid + 1
        } else if val > target {
            high = mid
        }
    }
    return -1
}

Binary search can be combined with jump search where in the last step, you instead use the binary search, which will make your algorithm even faster. as shown in the example