8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Sanchit Nov 27 '13 at 16:05
  • \$\begingroup\$ Yes ofc. Hold on. :) \$\endgroup\$ – WonderWorld Nov 27 '13 at 16:06
  • \$\begingroup\$ 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. \$\endgroup\$ – WonderWorld Nov 27 '13 at 16:26
8
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – WonderWorld Nov 27 '13 at 18:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Sanchit Nov 27 '13 at 19:22
6
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – WonderWorld Nov 27 '13 at 19:16
  • \$\begingroup\$ @Xbit This link has a pretty good description of wht Arrays.binary search is good: htmlgoodies.com/beyond/java/… \$\endgroup\$ – rolfl Nov 27 '13 at 19:25
  • \$\begingroup\$ 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 \$\endgroup\$ – Simon Forsberg Nov 27 '13 at 19:45
  • \$\begingroup\$ Copy-paste problem.... hmmm. \$\endgroup\$ – rolfl Nov 27 '13 at 20:21
1
\$\begingroup\$

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
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Could you also explain why this is better and how the original code fails to meet this level of optimization? \$\endgroup\$ – dfhwze Jul 5 at 4:32
  • \$\begingroup\$ 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. \$\endgroup\$ – KunYu Tsai Jul 5 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.