Interpolation Search Algorithm
Interpolation search algorithm is an advanced searching technique that works specifically on uniformly distributed sorted arrays or lists. It is an improvement over the binary search algorithm, which eliminates half of the remaining items in each iteration. The main idea behind the interpolation search is to estimate the position of the target value in the array, based on the values of the first and last elements, and the target value itself. This estimation is done using a linear interpolation formula, which calculates the probable position of the target value, allowing the search to potentially skip over a large number of irrelevant elements, thus significantly reducing the time complexity of the search.
In the interpolation search algorithm, the initial position is calculated using the formula: position = low + ((target - array[low]) * (high - low) / (array[high] - array[low])). Here, low and high represent the indices of the first and last elements of the current search range, while target is the value to be searched. If the calculated position is within the search range and the value at the calculated position is equal to the target value, the search is successful, and the index of the target value is returned. If the value at the calculated position is less than the target value, the search range is updated to start from the next element after the calculated position, i.e., low = position + 1. Conversely, if the value at the calculated position is greater than the target value, the search range is updated to end at the element before the calculated position, i.e., high = position - 1. The algorithm repeats this process until the target value is found or the search range becomes empty, indicating that the target value is not present in the array. The interpolation search algorithm boasts an average case time complexity of O(log log n) for uniformly distributed data, which is better than the binary search's O(log n) complexity. However, in the worst case, the interpolation search can degrade to O(n) complexity, which is slower than the binary search.
package InterpolationSearch
import (
"math/rand"
"testing"
"time"
)
func InterpolationSearch(array []int, number int) int {
minIndex := 0
maxIndex := len(array) - 1
for minIndex <= maxIndex && number >= array[minIndex] && number <= array[maxIndex] {
midIndex := minIndex + (number-array[minIndex])*(maxIndex-minIndex)/(array[maxIndex]-array[minIndex])
midItem := array[midIndex]
if midItem == number {
return midIndex
} else if midItem < number {
minIndex = midIndex + 1
} else if midItem > number {
maxIndex = midIndex - 1
}
}
return -1
}
func SortArray(array []int) {
for itemIndex, itemValue := range array {
for itemIndex != 0 && array[itemIndex-1] > itemValue {
array[itemIndex] = array[itemIndex-1]
itemIndex -= 1
}
array[itemIndex] = itemValue
}
}
func TestInterpolationSearch(t *testing.T) {
random := rand.New(rand.NewSource(time.Now().UnixNano()))
array := make([]int, random.Intn(100-10)+10)
for i := range array {
array[i] = random.Intn(100)
}
SortArray(array)
for _, value := range array {
result := InterpolationSearch(array, value)
if result == -1 {
t.Fail()
}
}
}
