Binary search for inserting in array

Question

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] < 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 
 }
 }
 }
 public void display() { // display array contents
 for (int j = 0; j < nElems; j++) { // for each element,
 System.out.print(a[j] + " "); // display it
 }
 System.out.println("");
 }
 public void insert(long value) { // put element into array
 binaryInsert(value);
 int j = curIn;
 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.
 }
}
public static void main(String[] args) {
 // TODO code application logic here
 int maxSize = 100; // array size
 OrdArray arr; // reference to array
 arr = new OrdArray(maxSize); // create array
 arr.insert(77); // insert 10 items
 arr.insert(99);
 arr.insert(44);
 arr.insert(55);
 arr.insert(22);
 arr.insert(88);
 arr.insert(11);
 arr.insert(00);
 arr.insert(66);
 arr.insert(33);
 arr.display(); 
}

Feedback appreciated.

• Sanchit: Can you also post the other variables that aren't mentioned in this function? It will help with the code review :) nElems, data type of curIn, declaration of a[] and whatever else you think is necessary. Also, this function is just supposed to return the index where the element should be inserted, correct?
• WonderWorld: Yes ofc. Hold on. :)
• WonderWorld: Yes that is correct. It's for returning the index to insert. It's a modified one for searching for a particular value, from the book i'm reading.

Answer 1

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

• WonderWorld: It looked a lot more wonkier when i saw it this morning. :) Your corrections work fine, except when there are no elements in the array, it starts inserting at index 1; Not sure how to fix that without an extra if statement saying if nElements == 0 --> return curIn; What do you mean at point 3 moving base case to beginning?
• Sanchit: Base case sort of means stuff that you can use to immediately exit the function. It's stuff you know to be true / the basis for the rest of your fuction to work. Like for fibonacci numbers base case is fib(0) = 0 and fib(1) = 1. You hardcode this in so that the rest of your function works.

Answer 2

There are a couple of things I think you should consider, on top of what Sanchit has pointed out.

The two things I can see are:

• why are you 'reinventing the wheel'
• if you have to do your own binary search, there are some things you should do right

Not-Reinventing-the-wheel

The 'right' way to do this is (and throw away your binary search code):

public void insert(long value) throws Exception { // put element into array
 if (nElems == MAX)
 throw new IllegalStateException("Can not add more elements.");
 int j = Arrays.binarySearch(a, 0, nElems, value);
 if (j < 0) {
 // this is a new value to insert (not a duplicate).
 j = - j - 1;
 }
 System.arraycopy(a, j, a, j+1, nElems - j);
 a[j] = value;
 nElems++;
}

Re-inventing the wheel

If you have to reinvent this wheel (it's homework, or something), then consider this:

• curIn is redundant, and should be the return value of your binarySearch function.
• the 'standard' in Java is to return the position of the value in the array, or, if the value does not exist in the array, return - ip - 1 where 'ip' is the 'insertion point' or where the new value should be. i.e. in the array [1, 2, 4, 5] a binary search for '4' should return '2' (4 is at position 2). A search for '3' should return '-3' because - (-3) - 1 is +3 - 1 or 2 which is the place the 3 should go if it is inserted. This allows a single binary search to produce the answer to two questions: is it in the array, and if it is, where is it? and also if it isn't, where should it go?
• technically your code has a slight bug for large values of MAX.... your binary search should do upperbound + lowerbound >>> 1 because that will give the right values if/when upperbound + lowerbound overflows.

• WonderWorld: It's about Re-inventing the wheel. :) The book i am reading states: "The techniques used in this chapter, while unsophisticated and comparatively slow are nevertheless worth examining." The code i have written is just as an exercise. With curIn is redundant and should be the return value. I thought it is the return value of my function? I don't understand how a search for 3 can return -3.
• rolfl: @Xbit This link has a pretty good description of wht Arrays.binary search is good: htmlgoodies.com/beyond/java/…
• Simon Forsberg: A note I'm not sure how relevant it is, but it is a better practice to throw an IllegalStateException instead of declaring throw Exception. You should be as specific as possible in "throws" declarations
• rolfl: Copy-paste problem.... hmmm.

Answer 3

This is a simpler way.

EDIT: The original way works fine. With regards to my solution, it's just with less code. The algorithm itself covers all the cases and we don't need to put if-else conditions to catch edge cases.

fun searchInsert(array: IntArray, num: Int): Int {
 var head = 0
 var tail = array.lastIndex
 while (head <= tail) {
 var mid = (head + tail) / 2
 if (num == array[mid])
 return mid
 else if (num > array[mid]) {
 head = mid + 1
 } else {
 tail = mid - 1
 }
 }
 return head
}

• dfhwze: Could you also explain why this is better and how the original code fails to meet this level of optimization?
• KunYu Tsai: Hi @dfhwze. Thanks for the reminder and I'm sorry I didn't explain it in the first place. I have added more explanation to it.