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

In summary: They must have changed it in Java 5.0.And I agree with the ArrayList, Vector is a legacy class and should be avoided unless you are required to use it for some reason.Sorry, I've been doing C# exclusively for the past 6 months and i use primitives in generic collections all the time. They must have changed it in Java 5.0.And I agree with the ArrayList, Vector is a legacy class and should be avoided unless you are required to use it for some reason.In summary, the conversation discusses the need to write a method for adding an integer to a sorted array of integers. The code for searching an integer in the array is also provided. The individual is seeking help in writing the code to
  • #1
pumas
15
0
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 :smile:
 
Technology news on Phys.org
  • #2
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.
 
  • #3
He wants to add an item to a list, not delete it, so shouldn't that be:

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

?
 
Last edited:
  • #4
Thanks for your help
 
  • #5
Jeff Reid said:
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.
 
  • #6
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.
 
Last edited:
  • #7
-Job- said:
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)?
 
  • #9
-Job- said:
Use the Vector class:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Vector.html
Code:
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.
 
  • #10
haki said:
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.
 

1. How do you sort an array in Java?

To sort an array in Java, you can use the Arrays.sort() method. This method takes in the array as a parameter and uses the QuickSort algorithm to sort the elements in ascending order.

2. Can I sort an array in descending order in Java?

Yes, you can sort an array in descending order in Java by using the Arrays.sort() method and passing in a comparator that sorts the elements in reverse order.

3. What is the time complexity of sorting an array in Java using Arrays.sort()?

The time complexity of sorting an array in Java using Arrays.sort() is O(n log n). This is because the QuickSort algorithm has an average time complexity of O(n log n) and the Arrays.sort() method uses this algorithm to sort the elements.

4. Can I sort an array of custom objects in Java?

Yes, you can sort an array of custom objects in Java by implementing the Comparable interface in your custom class and overriding the compareTo() method. This method will define the logic for comparing two objects and will be used by the Arrays.sort() method to sort the array.

5. Are there any other ways to sort an array in Java?

Yes, there are other ways to sort an array in Java such as using the Collections.sort() method, which is similar to the Arrays.sort() method but can be used for collections like ArrayList and LinkedList. You can also implement your own sorting algorithm or use a third-party library for sorting.

Similar threads

  • Programming and Computer Science
Replies
20
Views
1K
  • Programming and Computer Science
Replies
2
Views
524
  • Programming and Computer Science
Replies
10
Views
3K
  • Programming and Computer Science
Replies
5
Views
2K
  • Programming and Computer Science
Replies
7
Views
2K
  • Programming and Computer Science
Replies
4
Views
2K
  • Programming and Computer Science
Replies
3
Views
3K
  • Programming and Computer Science
2
Replies
46
Views
8K
  • Programming and Computer Science
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
18
Views
1K
Back
Top