patternjavaMinor

Binary search for inserting in array

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

searcharraybinaryforinserting

Problem

I have written a method that uses binary search to insert a value into an array.

It is working, but i would like to get a second opinion to see if i didn't write too much code for it. aka doing same thing twice for example.

The code looks for the right index for insertion and is called by an insert method that uses that index value to insert.

Here is the code:

```
public class OrdArray {

final private long[] a; // ref to array
int nElems; // number of dataitems
int curIn;
//----------------------------------------------------------------------

public OrdArray(int max) { // constructor
a = new long[max]; // create array
nElems = 0;
}

public int binaryInsert(long insertKey) {
int lowerBound = 0;
int upperBound = nElems - 1;

while (true) {
curIn = (upperBound + lowerBound) / 2;
if (nElems == 0) {
return curIn = 0;
}
if (lowerBound == curIn) {
if (a[curIn] > insertKey) {
return curIn;
}
}
if (a[curIn] upperBound) {
return curIn += 1;
}
} else if (lowerBound > upperBound) {
return curIn;
} else {
upperBound = curIn - 1; // its in the lower
}
}
}

public void display() { // display array contents
for (int j = 0; j j; k--) { // move bigger ones one up.
a[k] = a[k - 1];
}
a[j] = value; // insert value
nElems++; // increment size.
}
}

public static void main(String[] args) {
// TODO code application logic here
int maxSize = 100; // array size
OrdArray arr;

Solution

Here is my version of your code.

You never use "max" so I used it by throwing an exception if you are trying to insert too many elements.

You should make everything that shouldn't be public; private.

In your binaryInsert() you should move your base case to the begining.

-
Your binaryInsert() is a bit wonky but it works. I think this would do but I haven't checked it. Looks a bit neater and has one unnecessary if removed.

public int binaryInsert(long insertKey) {
   if (nElems == 0)
     return 0;
   int lowerBound = 0;
   int upperBound = nElems - 1;
   int curIn = 0;
   while (true) {
     curIn = (upperBound + lowerBound) / 2;
     if (a[curIn] == insertKey) {
       return curIn;
     } else if (a[curIn]  upperBound)
         return curIn + 1;
     } else {
       upperBound = curIn - 1; // its in the lower
       if (lowerBound > upperBound)
         return curIn;
     }
   }
 }

-
Just use methods that return things directly. Don't need to store them in a temporary variable first. Talking about curIn here in your insert function.

-
If you want to return something (like an object) as a String or print something out. You should override the toString() method as I have done. Then you can just call System.out.println(arr.toString()) whenever you want to print the Object.

-
The whole point of doing a binary insert would be to quickly find out where to insert an element. Your implementation does this, however your implementation isn't super useful because you have to move each and every element foward by one. A double linked list (as usually taught in C++ classes) is ideal for your implementation of this better version of insertion sort. The java equivalent of a doubly linked list is a LinkedList. Which will give you much better performance as you will not need to move elements forward by one.

.

public class OrdArray {

  final private long[] a; // ref to array
  private int nElems; // number of dataitems
  private final int MAX;

  // ----------------------------------------------------------------------

  public OrdArray(int max) { // constructor
    this.MAX = max;
    a = new long[MAX]; // create array
    nElems = 0;
  }

  private int binaryInsert(long insertKey) {
    if (nElems == 0) {
      return 0;
    }

    int lowerBound = 0;
    int upperBound = nElems - 1;

    while (true) {
      int curIn = (upperBound + lowerBound) / 2;
      if (lowerBound == curIn) {
        if (a[curIn] > insertKey) {
          return curIn;
        }
      }
      if (a[curIn]  upperBound) {
          return curIn += 1;
        }
      } else if (lowerBound > upperBound) {
        return curIn;
      } else {
        upperBound = curIn - 1; // its in the lower
      }
    }
  }

  @Override
  public String toString() { // display array contents
    StringBuffer sb = new StringBuffer();
    for (int j = 0; j  j; k--) { // move bigger ones one up.
      a[k] = a[k - 1];
    }
    a[j] = value; // insert value
    nElems++; // increment size.
  }
}

I'm sure I didn't get everything you need to improve on but hopefully that is atleast one step forward in the right direction. :)

Code Snippets

public int binaryInsert(long insertKey) {
   if (nElems == 0)
     return 0;
   int lowerBound = 0;
   int upperBound = nElems - 1;
   int curIn = 0;
   while (true) {
     curIn = (upperBound + lowerBound) / 2;
     if (a[curIn] == insertKey) {
       return curIn;
     } else if (a[curIn] < insertKey) {
       lowerBound = curIn + 1; // its in the upper
       if (lowerBound > upperBound)
         return curIn + 1;
     } else {
       upperBound = curIn - 1; // its in the lower
       if (lowerBound > upperBound)
         return curIn;
     }
   }
 }

public class OrdArray {

  final private long[] a; // ref to array
  private int nElems; // number of dataitems
  private final int MAX;

  // ----------------------------------------------------------------------

  public OrdArray(int max) { // constructor
    this.MAX = max;
    a = new long[MAX]; // create array
    nElems = 0;
  }

  private int binaryInsert(long insertKey) {
    if (nElems == 0) {
      return 0;
    }

    int lowerBound = 0;
    int upperBound = nElems - 1;

    while (true) {
      int curIn = (upperBound + lowerBound) / 2;
      if (lowerBound == curIn) {
        if (a[curIn] > insertKey) {
          return curIn;
        }
      }
      if (a[curIn] < insertKey) {
        lowerBound = curIn + 1; // its in the upper
        if (lowerBound > upperBound) {
          return curIn += 1;
        }
      } else if (lowerBound > upperBound) {
        return curIn;
      } else {
        upperBound = curIn - 1; // its in the lower
      }
    }
  }

  @Override
  public String toString() { // display array contents
    StringBuffer sb = new StringBuffer();
    for (int j = 0; j < nElems; j++) { // for each element,
      sb.append(a[j] + " "); // display it
    }
    sb.append(System.lineSeparator());
    return sb.toString();
  }

  public void insert(long value) throws Exception { // put element into array
    if (nElems == MAX)
      throw new Exception("Can not add more elements.");
    int j = binaryInsert(value);
    int k;
    for (k = nElems; k > j; k--) { // move bigger ones one up.
      a[k] = a[k - 1];
    }
    a[j] = value; // insert value
    nElems++; // increment size.
  }
}

Context

StackExchange Code Review Q#36221, answer score: 8

Revisions (0)

No revisions yet.