Interpolation searches for the entity in the given sortedData. if the entity is present, it will return the index of the entity, if not -1 will be returned. see: https://en.wikipedia.org/wiki/Interpolation_search Complexity Worst: O(N) Average: O(log(log(N)) if the elements are uniformly distrib
(sortedData []int, guess int)
| 13 | // |
| 14 | // fmt.Println(InterpolationSearch([]int{1, 2, 9, 20, 31, 45, 63, 70, 100},100)) |
| 15 | func Interpolation(sortedData []int, guess int) (int, error) { |
| 16 | if len(sortedData) == 0 { |
| 17 | return -1, ErrNotFound |
| 18 | } |
| 19 | |
| 20 | var ( |
| 21 | low, high = 0, len(sortedData) - 1 |
| 22 | lowVal, highVal = sortedData[low], sortedData[high] |
| 23 | ) |
| 24 | |
| 25 | for lowVal != highVal && (lowVal <= guess) && (guess <= highVal) { |
| 26 | mid := low + int(float64(float64((guess-lowVal)*(high-low))/float64(highVal-lowVal))) |
| 27 | |
| 28 | // if guess is found, array can also have duplicate values, so scan backwards and find the first index |
| 29 | if sortedData[mid] == guess { |
| 30 | for mid > 0 && sortedData[mid-1] == guess { |
| 31 | mid-- |
| 32 | } |
| 33 | return mid, nil |
| 34 | |
| 35 | } |
| 36 | |
| 37 | // adjust our guess and continue |
| 38 | if sortedData[mid] > guess { |
| 39 | high, highVal = mid-1, sortedData[high] |
| 40 | |
| 41 | } else { |
| 42 | low, lowVal = mid+1, sortedData[low] |
| 43 | } |
| 44 | |
| 45 | } |
| 46 | |
| 47 | if guess == lowVal { |
| 48 | return low, nil |
| 49 | } |
| 50 | return -1, ErrNotFound |
| 51 | } |
no outgoing calls