Having trouble insert/sorting arrays with binary searching.

[bh-chobo]

The client will be making an array and adding numbers to it. Its my job/objective to make sure that when the client passes it into the array - it is sorted in non-decreasing order.

Note - i just finally learned about binary search and still trying to toy around with it. Have to utilize it - can't use sequential search as its resource consuming.

So i'm basically just starting off with the client program VAGUELY - (you get the jist) - doing basic things like,

list.add(10);
list.add(9);
list.add(11);

basically just shoving value 10,9,11 into my program.

So, ideally - i want it the array to sort itself out. (without using array.sort)

array - [9.10.11]

Though i'm running into issues - i think my logic/thoughts/code in the ADD method (below) is messed. But i've hit a stump.. and honestly can't get around it... I called indexOf to use binary search to locate the index for the value, and so found that.

Simply insert into that index? But it doesn't seem to comply.

Might have been misunderstanding something. I got the idea.. just can't think of the right code to put it into performance.


Took 2 quarter break from java, and decided to jump back into it for the next level class as it was a minor requirement -so my coding IS indeed flakey most definetly, so any assistance small or large would be greatly appreciated.





import java.util.*;

public class SortArrayList {
private int[] elementData;
private int size;

public static final int MAX_CAP = 100;

public SortArrayList() {
this(MAX_CAP);
}

public SortArrayList(int capacity) {
elementData = new int[capacity];
size = 0;
}

// Use binary search to look for a requested value.
public int indexOf(int value) {

int index = Arrays.binarySearch(elementData,0,size, value);
return index;

}



public void add(int value) {
int indexLocation = indexOf(value); // look for index of value wanted to be inserted.


if(indexLocation > 0) {
size++;
elementData[indexLocation] = value;
}else{
size++;
elementData[-(indexLocation-1)] = value;
}
}

[dlorde]

Can you explain clearly what you are trying to do?

It sounds like you want to insert values into an array, keeping it sorted. So if the value already exists in the array (indexOf returns 0 or greater), you can either insert it again, giving a duplicate, or ignore it. If the value doesn't exist in the array (indexOf returns a negative number) that you can use the return value to find out where to insert it.

But in both instances inserting a value means you have to move any existing values that are in the way, to make room for the new value. Unless the new value is greater than any existing values, you have to move all the values that are greater one position up to make room for it.

It is better to have an approximate answer to the right question than an exact answer to the wrong one...
J. Tukey

[Xeel]

So are you against any kind of sort after insert or just the array.sort() method?