Golang
Golang

 

 

Interpolation search is an efficient search algorithm for uniformly distributed sorted arrays. Unlike binary search, which divides the search interval in half, interpolation search estimates the position of the sought value based on the values at the ends of the interval.

Go Implementation

package main

import (
    "fmt"
)

// InterpolationSearch function implements the interpolation search algorithm.
func InterpolationSearch(arr []int, x int) int {
    low := 0
    high := len(arr) - 1

    for low <= high && x >= arr[low] && x <= arr[high] {
        // Estimate the position of the element
        if low == high {
            if arr[low] == x {
                return low
            }
            return -1
        }

        pos := low + (x-arr[low])*(high-low)/(arr[high]-arr[low])

        if arr[pos] == x {
            return pos
        }

        if arr[pos] < x {
            low = pos + 1
        } else {
            high = pos - 1
        }
    }
    return -1
}

func main() {
    arr := []int{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}
    x := 70

    result := InterpolationSearch(arr, x)

    if result != -1 {
        fmt.Printf("Element %d found at index %d.\n", x, result)
    } else {
        fmt.Printf("Element %d not found in the array.\n", x)
    }
}

Program Structure Explanation

  • Package Declaration: The program begins with the package declaration, package main, which defines the main package for the Go program.
  • Imports: The fmt package is imported to enable formatted I/O operations.
  • InterpolationSearch Function:
    • Inputs: The function accepts a sorted integer array arr and the integer value x to search for.
    • Logic: It initializes low and high indices. Using a loop, it estimates the position of x based on interpolation.
    • Return: If found, it returns the index of x; otherwise, it returns -1.
  • Main Function:
    • Defines a sorted array and the element to search for.
    • Calls the InterpolationSearch function and prints the result.

Conclusion

The interpolation search algorithm can be more efficient than binary search for uniformly distributed datasets. Its performance, however, depends on the distribution of the data, making it less effective for non-uniform datasets.

 

By Aditya Bhuyan

I work as a cloud specialist. In addition to being an architect and SRE specialist, I work as a cloud engineer and developer. I have assisted my clients in converting their antiquated programmes into contemporary microservices that operate on various cloud computing platforms such as AWS, GCP, Azure, or VMware Tanzu, as well as orchestration systems such as Docker Swarm or Kubernetes. For over twenty years, I have been employed in the IT sector as a Java developer, J2EE architect, scrum master, and instructor. I write about Cloud Native and Cloud often. Bangalore, India is where my family and I call home. I maintain my physical and mental fitness by doing a lot of yoga and meditation.

Leave a Reply

Your email address will not be published. Required fields are marked *

error

Enjoy this blog? Please spread the word :)