Return to Revisions

Here is my version of your code.

1. You never use "max" so I used it by throwing an exception if you are trying to insert too many elements.
2. You should make everything that shouldn't be public; private.
3. In your binaryInsert() you should move your base case to the begining.
4. 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] < 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;
         }
       }
     }

5. 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.

6. 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.

7. 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 [http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html]. 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] < 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.
  }
}

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. :)