How can I add an integer to a sorted array using binary search in Java?

[pumas]

Hello,

I need to write a method that adds an interger to a sorted array of integers. I'm using the following code to search for an interger in the array

private static int binarySearch(int[] list, int key,
int low, int high) {
while (low <= high) {
int mid = (low + high) / 2;
int midVal = list[mid];

if (midVal < key) {
low = mid + 1;
} else if (midVal > key) {
high = mid - 1;
} else {
return mid; // key found
}
}
return -(low + 1); // key not found.
}

I have not done programming in a long time, so I'm very confused on how to write the code to insert a number and preserved the sorted order.
I would appreciate any help

Thanks

 

[chaoseverlasting]

You could search for the next largest number, store it in a temporary variable and:

1. Replace the number you just stored in the temp variable with the one you want to insert.
2. Use the temporary variable to shift the array down by one.

Eg:
for(i=maxval;i>x;i--) /*x is the position of the next largest number maxval is the largest index number of the array*/

{
arr[x-1]=arr[x];
}
arr=j; //j is the number you want to insert and i=x now

This is good enough for a static array, but for a dynamic one i guess you'd need to create a new array with one more element. I can't help you in the actual coding cause I only know c++. The logic, however, should be the same.

 

[rcgldr]

He wants to add an item to a list, not delete it, so shouldn't that be:

arr[x+1]=arr[x];

?

 

[pumas]

Thanks for your help

 

[chaoseverlasting]

He wants to add an item to a list, not delete it, so shouldn't that be:

arr[x+1]=arr[x];

?

Since the array is static, one item will be deleted. If the array is dynamic, and you want to add an item in the middle, then you use the linked list approach, which is totally different.

 

[-Job-]

If you're not required to use an array as your data structure then you should use a Vector instead, which is basically an array that automatically grows when necessary.

Also, if this is a school assignment then you might get extra points if you code your binary search as a recursive function.

 

[chaoseverlasting]

If you're not required to use an array as your data structure then you should use a Vector instead, which is basically an array that automatically grows when necessary.

Also, if this is a school assignment then you might get extra points if you code your binary search as a recursive function.

How would you do that (the vector part)?

 

[-Job-]

Use the Vector class:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Vector.html

Vector<int> MyVector = new Vector<int>(initialSize)
//add to vector:
MyVector.add(200);
//or insert at location:
MyVector.insertElementAt(232, 0);

The Vector automatically grows.

 

[haki]

Use the Vector class:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Vector.html

Vector<int> MyVector = new Vector<int>(initialSize)
//add to vector:
MyVector.add(200);
//or insert at location:
MyVector.insertElementAt(232, 0);

The Vector automatically grows.

Vector<int> MyVector is not a valid code

Vector<Integer> is valid, since you cannot pass primitives into the <> tags.

It is generally recommended to use ArrayList instead of Vector class.

That is one can do

ArrayList<Integer> integerList = new ArrayList<Integer>();
integerList.add(5);
integerList.add(6);
...add as many as you like the list will grow as needed.

 

[-Job-]

Vector<int> MyVector is not a valid code
Vector<Integer> is valid, since you cannot pass primitives into the <> tags.

Sorry, I've been doing C# exclusively for the past 6 months and i use primitives in generic collections all the time.