Golang Program to Implement Interpolation Search


February 27, 2022, Learn eTutorial
1272

For a better understanding of this example, we always recommend you to learn the basic topics of Golang programming listed below:

There are different types of searching algorithms. But in this section, we’ll be discussing an improvement over the traditional Binary Search approach called Interpolation Search. Here we are explaining how to write a GO program to search an element from an array by using Interpolation Search.

The main difference between interpolation search algorithm and binary search is that in the case of binary search, it starts the search from the middle of the array. But interpolation search algorithm tries to find the element where it is more likely present. For the proper working of the algorithm, the elements of the array must be sorted and uniformly distributed. 

The interpolation searching is almost similar to that of searching a particular name in the telephone directory or a particular word in the English dictionary, where data must be uniformly distributed. For example, In the case of the telephone directory, all the names starting with a or b will be at the beginning of the directory, and all the names starting with o and p will probably lie somewhere in the middle. On the other hand, names starting with x, y and z will be at the very end of the directory. So we can start our search at a different position each time, based on the element we need to search. 

In a uniformly distributed sorted array, smaller numbers will lie at the beginning of the array whereas larger numbers should lie towards the end of the array. So, whenever Interpolation Search wants to search for a larger number from this array, it will start the search somewhere at the end of the array and In the case of smaller numbers; start the search somewhere at the beginning of the array.

How to implement Interpolation Search 

In this GO program, we are importing the “fmt” package to include some standard libraries into the program. After that Main function starts, inside the main, we are doing the whole program. Note that the time complexity of the Interpolation search algorithm is Ο(log (log n)).

In this GO program, we accept the user's values using the fmt.scanln()  and fmt.println()  methods which are defined under the fmt package. In order to use these functions, we need to import the “fmt” package.

Here variable A holds the array elements. Other variables n and key are used as the size of the array and searching element respectively. Use for loop to read array elements. Note that Interpolation search only works when elements are in uniformly distributed sorted order. 

The variables low and high are used as function parameters. Assign low =0, High=n-1 and perform interpolation search within an iteration loop by calling function InterpolationSearch(A,key) and assign function return value into the variable index. Here we calculate the middle element mid using the formula : 

mid = low + ((key – A[low]) * (high – low) / (A[high] – A[low]))

where A[low…high] is our search space, and the key is the given element to be searched. 

If the search element key matches with the middle element, return the middle element index. Otherwise, check if the key is greater than the middle element. If so, make low = mid + 1. Else assign high = mid – 1. if the index is equal to -1, print Element not found. Otherwise, print the index of the element found. i.e.; index +1 

Given below are the steps which are used in the Go program to implement Interpolation search. 

ALGORITHM:

STEP 1: Import the package fmt
STEP 2: Open the main() to start the program, GO program execution starts with the main()
STEP 3: Declare the variable n, x, temp, Low, High, and result.
STEP 4: Read the size of the array as n.
STEP 5: Define the array A[]. 
STEP 6: Read the A[] array elements by using a for a loop.
STEP 7: Read the number to be searched as key.
STEP 8: Assign the Low as 0 and High as the number of terms n-1.
STEP 9:  Call the function InterpolationSearch(A, key) and assign the return value to the index.
STEP 10: Check using an 'if' condition that the index is equal to -1. If so, print Element not found 
STEP 11: Otherwise, print the position of the element found. i.e.; index +1
STEP 12: Exit

Steps To Implement InterpolationSearch(A, key) Function

STEP 1: Declare the variables mid as middle element, low and high as an index of the array.
STEP 2: Initialize low = 0 and high = n-1.
STEP 3: Open the 'for loop' and check the condition A[low] < key and A[high] > key. If the condition is true then do the following steps.
STEP 4: Calculate the middle element mid using the formula; mid = low + ((key-A[low])*(high-low))/(A[high]-A[low]).
STEP 5: Check using an 'if' condition that search element key is equal to the Array middle element mid. If so, returns the value of mid and quit this function.
STEP 6: Using an 'if' condition check, the Array middle element mid is less than key. If so, assign low = mid + 1.
STEP 7: Else check the Array middle element mid is greater than key if so high = mid -1.
STEP 8: Check using an 'if' condition that search element key is equal to the Array middle element mid. If so, returns the value of mid and quit this function.
STEP 9: Check if A[low] is equal to the search element key, if so, return low.
STEP 10: Else check if A[high] is equal to the search element key, if so, return high. Otherwise, return -1.

Given below is the source code of the Go program to search an element in an integer array using the Interpolation search algorithm. The output will show the position of the element in the array.
 

Golang Source Code

                                          package main
import "fmt"

//interpolation search method
func InterpolationSearch(A []int, key int)int{
 var mid int
 var low int
 low = 0
 var high int
 high = len(A) - 1

 for A[low] < key && A[high] > key {
  mid = low + ((key-A[low])*(high-low))/(A[high]-A[low])

  if A[mid] < key {
   low = mid + 1
  } else if A[mid] > key {
   high = mid - 1
  } else {
   return mid
  }
 }

 if A[low] == key {
  return low
 } else if A[high] == key {
  return high
 } else {
  return -1
 }

}

// main method
func main() {
         var key int
        var n int
        fmt.Println("Enter the size of the array")
 fmt.Scan(&n)
 A := make([]int, n, 100)
       fmt.Println("Enter elements of the array in uniform distributed and sorted order: ")
 for i := 0; i < n; i++ {
  fmt.Scan(&A[i])
 }
 fmt.Println("Enter the number to be searched")
 fmt.Scan(&key;)
 var index int
 index = InterpolationSearch(A, key)
 if index == -1 {
  fmt.Println("Element not found !")
 } else {
 fmt.Println("The element found at", index+1)
 }
}

                                      

OUTPUT

Enter the size of the array
5
Enter elements of the array in uniform distributed and sorted order: 
2
4
6
8
10
Enter the number to be searched
8
The element found at 4