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)