the output of my Interpolation search is wrong, why?-CodePudding

I have to write a Program which is called "Interpolation search". I came so far but now I am stuck and can´t find the error in my code. The method split() makes a problem. This method should give me the index to split. I just typed the formula in this method. Now the big problem is, I every time get 1 as an output which is always the "leftBoundary". For example, I write in my terminal java Search 4 1 2 3 4 5 6 then I get every time 1. Why? what is wrong?

edit: I was asked to explain what the split method does in Detail: This method uses the formula (look at added picture) to determine where to split the (sorted) array and returns the corresponding index. In the picture: v = wantedValue, l = leftBoundary, r = rightBoundary enter image description here

import java.util.Scanner;

public class Search {

    // This method uses the formula (look at added picture) to determine where to split the (sorted) array and returns the corresponding index.
    private static int split(int[] haystack, int needle, int left, int right) {
        if(haystack[right] == haystack[left]) {
            return left;
        }else {
        needle = left   ((needle - haystack[left]) / (haystack[right] - haystack[left])) * (right - left);
        return needle;
        }
    }
    private static int search(int[] haystack, int needle) {

        return -1;
    }

    public static void main(String[] args) {

        int[] array = new int[args.length];
        int leftBoundary = 1;
        int rightBoundary = array.length - 1;
        int wantedValue = Integer.parseInt(args[0]);


        for(int i = 1; i < args.length; i  ) {
           array[i] = Integer.parseInt(args[i]);
        }

         int splitAtIndex = split(array, wantedValue, leftBoundary, rightBoundary);
         System.out.println(splitAtIndex);
    }
}

I tried to debug but with no success and also searched here on stackoverflow. Many have question to interpolation search, but the answers are complex and unfortunately do not explain the exact problem I have

CodePudding user response：

Apart from the comment, by @user16320675, to your question, your initialization is wrong.

The first [command-line] argument is the value of wantedValue. The remaining [command-line] arguments are the elements of array.

Also, leftBoundary should be 0 (zero) and not 1 (one) since you probably want to search the whole array.

Consider the following code:

public class Search {

    private static int split(int[] haystack, int needle, int left, int right) {
        if (haystack[right] == haystack[left]) {
            return left;
        }
        else {
            return (int) (left   ((double) (needle - haystack[left]) / (haystack[right] - haystack[left])) * (right - left));
        }
    }

    public static void main(String[] args) {
        int[] array = new int[args.length - 1];
        int leftBoundary = 0;
        int rightBoundary = array.length - 1;
        int wantedValue = Integer.parseInt(args[0]);
        for (int i = 1; i < args.length; i  ) {
            array[i - 1] = Integer.parseInt(args[i]);
        }
        int splitAtIndex = split(array, wantedValue, leftBoundary, rightBoundary);
        System.out.println(splitAtIndex);
    }
}

I removed the import statement since Scanner is not used. I also removed method search since it is never called.

If I run the above code using your example [command-line] arguments, i.e.

4 1 2 3 4 5 6

then method search returns 3 — which is the index of the searched-for element in the array since 4 is the searched-for value and the array contains the numbers 1 to 6 (inclusive).

Of-course, the array being searched must be sorted.

Note that if the searched-for value is smaller than the first array element, i.e. the element at index 0 (zero), method search will return -1 (minus one) and if the searched-for value is greater than the last element in the array, method search will return the array length. Hence you can determine whether the searched-for value is not found in the array.

If the [command-line] arguments are:

4 1 2 3 5 6

then method search returns 2. Note that the searched-for value, i.e. 4, is not in the array.

It is probably also a good idea to check the parameters of method search, i.e. that right should not be less than left and that haystack contains at least one element.

CodePudding user response：

If you split the array into two sectors then you should assume the leftmost index is lower and rightmost index is higher. After passing the parameter to the interpolation search, then it functioned to find the searched one. In Java, it is easy to implement. Java gives the opportunity to create functions that work in better time complexity. Here is the implementation in Java.

import java.util.*;

class GFG {

public static int int_search(int my_arr[], int lower,
                                    int higher, int x)
{
    int position;

    if (lower <= higher && x >= my_arr[lower] && x <= my_arr[higher]) {

        position = lower
              (((higher - lower) / (my_arr[higher] - my_arr[lower]))
                * (x - my_arr[lower]));

        if (my_arr[position] == x)
            return position;

        if (my_arr[position] < x)
            return int_search(my_arr, position   1, higher,
                                    x);

        if (my_arr[position] > x)
            return int_search(my_arr, lower, position - 1,
                                    x);
    }
    return -1;
}

public static void main(String[] args)
{

    int my_arr[] = { 21,45,65,67,34,54,23,24,76,74,37,64};

    int n = my_arr.length;

    int x = 74;
    int index = int_search(my_arr, 0, n - 1, x);

    
    if (index != -1)
        System.out.println("The element you are trying to found at  "
                          index);
    else
        System.out.println("The element you are trying to found is not here.");
}

}

Thank you.