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.