Need code in Java with short comment to understand and output.

CompareSearch:Implement Interpolation Search algorithm from textbook (Algorithm 8.1) and the Binary Search algorithm from textbook (Algorithm 1.5). Try different problem instances against both algorithms to analyze best-case, average-case, and worstcase.

Compare the performances of both of the algorithms based on your results and how they compare to each other. I will attach both the algorithm. You can copy and modify the algorithm to answer this question.

It also need a report. The report should include different problem instances used and the analysis of performance of each algorithm and how compare against each other

ALGORITHM 1.5:

public static index binsearch(int n, keytype [] S, keytype x)

{

index location, low, high , mid ;

number denominator;

low = 1; high = n;

location = 0;

while (low <= high && location == 0) {

mid = {(low +high) /2];

if ( x == S [mid])

location = mid;

else if (x < S [mid] )

high = mid -1 ;

else

low = mid +1;

}

return location ;

}

ALGORITHM 8.1

Determine whether x is in the sorted array S of size n

Inputs positive integer n and sorted ( non decreasing order ) array of numbers S indexed from 1 to n

Outputs the location i of x in S; 0 if x is not in S

public static index interpsrch(int n, number [] S, number x)

{ index low, high, mid,i; number denominator;

low = 1; high = n; i = 0;

if (S[low] <= x <= S[high]) while (low <= high && i == 0) { denominator = S[high] - S[low]; if (denominator == 0) mid = low; else mid = low + [ ((x-S[low]) * (high - low)) / denominator] ; if (x == S [mid] ) i = mid; else if (x < S [mid]) high = mid -1; else low = mid +1; } return i ;

}