Golang Algorithm - Interpolation Search

 

 

 

 

 

보간 검색은 정렬된 배열의 값이 균일하게 분산되는 인스턴스에 대한 이진 검색보다 개선된 것입니다. 이진 검색은 항상 중간 요소로 이동하여 검사합니다. 한편, 보간 검색은 검색되는 키의 값에 따라 서로 다른 위치로 이동할 수 있다. 다음은 보간 검색 알고리즘을 사용하여 정수 배열에서 요소를 검색하는 Go 프로그램의 소스 코드입니다. 출력은 배열에 요소의 위치를 나타냅니다.

 

 

package main

import "fmt"


func interpolationSearch(array []int, key int) int{

	min, max := array[0], array[len(array) -1]
	low, high := 0, len(array)-1

	for {
		if key < min{
			return low 
		}

		if key > max{
			return high + 1 
		}

		var guess int 
		if high == low{
			guess = high 
		}else{
			size := high - low 
			offset := int(float64(size-1) * (float64(key-min) / float64(max-min)))
			guess = low + offset 
		}

		if array[guess] == key{
			for guess > 0 && array[guess-1] == key{
				guess--
			}
			return guess 
		}

		if array[guess] > key{
			high = guess -1 
			max = array[high]
		}else{
			low = guess + 1
			min = array[low]
		}


	}
}

func main(){
	items := []int{1,2,9,20,31,45,63,70,100}
	fmt.Println(interpolationSearch(items, 63))
	
}