CODEWITHSUNDEEP
javabinary-search
HappyUser
HappyUser

Reputation: 309

Return the insert position of an element into a sorted array with Binary Search Recursion

I want to return the position of an element from a sorted array if that element exist otherwise I want to return the insert position where the element should be inserted. Here is my code:

    public static int bs(int[] array, int left, int right, int elem) {
    if (left > right) {
        return left;
    } else {
        int middle;
        middle = (left + right) / 2;
        if (left == right) { // used to return the insert position
            return left;
        } else if (elem > array[middle]) {
            return bs(array, middle + 1, right, elem);
        } else if ((elem < array[middle])) {
            return bs(array, left, middle - 1, elem);
        } else {
            return middle; // element existed into array
        }
    }
}

For example:

array = [ 2 5 8 10], elem = 8 => will return 2

array = [ 2 5 8 10], elem = 6 => will return 1

array = [ 2 7 14 22 32 56 88 91 102], elem = 3 => will return 1 (but the above program returns 0)

Upvotes: 0

Views: 1114

Answers (2)

Serge Breusov
Serge Breusov

Reputation: 1396

Your mistake is removing array[middle] from split, when bs(left,middle-1). Instead, you need use bs(left,middle) and bs(middle+1,right). I added print to recursive calls and found it easily.

public static int bs(int[] array, int left, int right, int elem) {
    System.out.println("["+left+", "+right+"]");
    if (left > right) {
        return left;
    } else {
        int middle;
        middle = (left + right) / 2;
        if (left == right) { // used to return the insert position
            return left;
        } else if (elem > array[middle]) {
            return bs(array, middle + 1, right, elem);
        } else if ((elem < array[middle])) {
            return bs(array, left, middle, elem); //<-- was: middle-1
        } else {
            return middle; // element existed into array
        }
    }
}

Also I think this style would be better;)

public static int bs2(int[] array, int left, int right, int elem) {
    System.out.println("["+left+", "+right+"]");
    if (left >= right)
        return left;

    int middle;
    middle = (left + right) / 2;
    if (elem > array[middle])
        return bs(array, middle + 1, right, elem);
    if ((elem < array[middle]))
        return bs(array, left, middle, elem); //<--- was: middle-1
    return middle; // element existed into array
}

Upvotes: 1

Kreeks
Kreeks

Reputation: 1

I hope I got you right. This is my first post so please have mercy with me :).

At first i think array = [ 2 5 8 10], elem = 6 => will return 2 would be correct, because 6 > 5 so it would have the index 2. Or do you want to replace 5 with 6 ? If you want to replace remove the "//" of my comment.

public static int getPosition(int[] arr, int value)
{
    int position = 0;

    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] == value)
        {
            position = i;
            break;
        } else
            position = -1;
    }

    if (position == -1)
    {
        int[] arr2 = new int[arr.length + 1];
        System.arraycopy(arr, 0, arr2, 0, arr.length);
        arr2[arr.length] = value;

        Arrays.sort(arr2);
        position = getPosition(arr2, value);//-1;
    }
    return position;
}

public static void main(String[] args)
{

    int[] arr = { 2, 5, 8, 10 };

    System.out.println(getPosition(arr, 6));

}

Upvotes: 0

Related Questions