(arr, lo, hi, x)
| 1 | def interpolationSearch(arr, lo, hi, x): |
| 2 | |
| 3 | if (lo <= hi and x >= arr[lo] and x <= arr[hi]): |
| 4 | |
| 5 | |
| 6 | |
| 7 | pos = lo + ((hi - lo) // (arr[hi] - arr[lo]) *(x - arr[lo])) |
| 8 | |
| 9 | |
| 10 | |
| 11 | if arr[pos] == x: |
| 12 | |
| 13 | return pos |
| 14 | |
| 15 | if arr[pos] < x: |
| 16 | |
| 17 | return interpolationSearch(arr, pos + 1,hi, x) |
| 18 | if arr[pos] > x: |
| 19 | |
| 20 | return interpolationSearch(arr, lo,pos - 1, x) |
| 21 | |
| 22 | return -1 |
| 23 | |
| 24 | |
| 25 | arr = [10, 12, 13, 16, 18, 19, 20,21, 22, 23, 24, 33, 35, 42, 47] |