Interpolation to find the formula is: mid=low + (high - low) * (k - arr [low])/(arr [high] - arr [low]), then I have a few doubts:
The first:
(k - arr [low])/(arr [high] - arr [low]) are two type int number division, it is not the result of the almost is zero, which come of proportion?
The second:
(arr [high] - arr [low]), one thousand arr [high] and arr [low] are equal, the result is 0, that don't become divided by zero error,
The above question is when I debug the problems found, is I understand is wrong, or the algorithm itself is not to force, hope your bosses directions

CodePudding user response:

Lagrange interpolation, if you learned the Lagrange, you should know "Lagrange" is on the zero passage

CodePudding user response:

Oh, carefully Chou Chou, this is Newton interpolation

CodePudding user response:

refer to the second floor wanghui0380 response:

oh, carefully Chou Chou, this is Newton interpolation

Well, the first question is I understand is wrong, but the second question is that do exist, once appear array repeat number appears in addition to the zero error

CodePudding user response:

The forehead, Newton interpolation to calculate the slope, point (x, y) is not high, low,
Points a and b, as long as point a is not equal to point b, even if is a parallel to the x axis or parallel to the y axis is no matter of
Slope to 0 to have relationships (1, 0) (3, 0) not (2, 0)

CodePudding user response:

Brothers, interpolation search is the premise of sort an array is good, and the best situation is uniform, so the second question, the difference between the minimum and maximum number is 0, meaning the entire array are of the same number?
And the algorithm can be optimized, you can handle this kind of situation, but if there really is this kind of situation, that doesn't need to look up, not directly can be concluded as a result, the complexity of O (1) directly