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.
nElems
, data type ofcurIn
, declaration ofa[]
and whatever else you think is necessary. Also, this function is just supposed to return the index where the element should be inserted, correct? – Sanchit Nov 27 '13 at 16:05