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

Question

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)

Answer 1

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
}