Return to Answer

       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.

       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. Which will give you much better performance as you will not need to move elements forward by one.

.

  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;
      }
    }
  }

(Pretend this starts from 5)

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 int binaryInsert(long insertKey) {
    int lowerBound = 0;
    int upperBound = nElems;
    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 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;
      }
    }
  }