To compare search strategies on real data, a performance panel counts how many positions interpolation search looks at. values is sorted ascending with no repeats. Run exactly this search for target:
low = 0, high = values.length - 1, and guesses = 0.low <= high and values[low] <= target <= values[high]: compute pos, add 1 to guesses, and compare values[pos] with target. If equal, stop. If smaller, set low = pos + 1; if bigger, set high = pos - 1.pos is low when low === high, and otherwise low + Math.floor((target - values[low]) * (high - low) / (values[high] - values[low])).Write interpolationGuesses(values, target) that returns [index, guesses], where index is where the target was found, or -1 if the loop ended without finding it.
Input: values = [10,20,30,40,50,60,70,80,90,100], target = 70 Output: [6,1]
pos = 0 + Math.floor(60 * 9 / 90) = 6, which holds 70: one guess.
Input: values = [1,2,3,4,5,6,7,8,9,1000], target = 9 Output: [8,9]
The huge last value drags every guess to the left, so the guesses walk 0, 1, 2, ... 8.
0 <= values.length <= 1000-10^6 <= values[i], target <= 10^6Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #183 Count the Interpolation Guesses. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.