Recursive Insert via binary search

Question

I have a sorted array and want to recursively find a position for inserting an element. E.g. an array 2,4,5,6,7,8,12,35 with an insertion value of 3 and the algorithm should return the index of the position where the 3 has to be inserted (index 1). The following code works sometimes, and other times it gets stuck in an infinite loop. Eventually my brain feels like jelly and I ask for your help. This is the code:

private static int insertRec(int[] a, int e, int l, int r) {
    int mid = l + r / 2;
    if (l == r || a[mid] == e) return mid;
    if (e > a[mid]) insertRec(a, e, mid + 1, r);
    if (e < a[mid]) insertRec(a, e, l, mid - 1);
    return -1;

}

Edit with assumed working code:

private static int insertRec(int[] a, int e, int l, int r) {
    int mid = (l + r) / 2;
    if (l == r || a[mid] == e) return mid;
    else if (e > a[mid]) return insertRec(a, e, mid + 1, r);
    else if (e < a[mid]) return insertRec(a, e, l, mid - 1);
    return -1;

}

ale64bit · Accepted Answer · 2014-11-15 21:48:08Z

3

int mid = l + r / 2;

It should be

int mid = (l + r) / 2;

EDIT: moreover, you can check the description of the STL algorithm lower_bound which makes exactly what you want, as I understand. A implementation based on this would be like:

int lb(int a[], int last, int val) { // array, len of the array, element to insert
  int it, count, step;
  int first = 0;
  count = (last-first);
  while (count > 0) {
    it = first;
    step = count/2;
    it += step;
    if (a[it] < val) {
      first = ++it;
      count -= step+1;
    } else
      count = step;
  }
  return first;
}

EDIT2: your code has a few mistakes to work properly, among them:

in the second line you cannot check if a[mid] == e because the element you want to insert, may not exist in the array. This will cause to return -1 in several cases.
the infinite loop arises from the way of computing mid and later assigning mid+1 or mid-1.
because the element you want to insert may be equal to some elements in the array, you will be returning incorrectly, since you compare for both e > a[mid] and e < a[mid].

I advice you to take a look at this fantastic post about binary search. In any case, here's the algorithm trying to follow the more possible your style and using the info of the post. Hope it helps.

private static int insertRec(int[] a, int e, int l, int r) {
    int mid = l + (r - l) / 2;
    if (l == r) return l;
    else if (a[mid] < e) return insertRec(a, e, mid+1, r);
    else return insertRec(a, e, l, mid);
}

edited Nov 15, 2014 at 21:48

answered Nov 15, 2014 at 21:00

ale64bit

6,2723 gold badges27 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

gutenmorgenuhu Over a year ago

You are totally right about this (did I mention my jelly brain?) But that is not the entire solution to my problem. Take the array 0, 0, 0, 1, 2, 2, 3, 5, 7, 7 and try to insert a 3 with my algorithm. It produces -1

ale64bit Over a year ago

@gutenmorgenuhu check my edit. I didn't check your algorithm completely, just the obvious part.

gutenmorgenuhu Over a year ago

I thank you for your fast answer. The problem is, that your lb algorithm does not use binary search but performs a linear iteration.

ale64bit Over a year ago

@gutenmorgenuhu it uses a binary search, but it is implemented iteratively. You can easily convert it to a recursive version. I will check your code now.

gutenmorgenuhu Over a year ago

I have to check your code later. I am too brainwashed at the moment to properly understand what it is doing. I edited my question with a suggestion. The method now works a bit better but there are still cases, where an infinite loop occurs or a wrong insertion index is returned (0, 5, 5, 6, 6, 7, 7, 8, 9, 9 suggests an insertion an pos 0 and not at pos 1)

|

Collectives™ on Stack Overflow

Recursive Insert via binary search

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related