Thread: Having trouble insert/sorting array values w/ binary searching.

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,

PHP Code:

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.

PHP Code:


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;
            }
    } 


First of all you need to have a look at the binarySearch definition.

binarySearch

public static int binarySearch(int[] a, int key)

Searches the specified array of ints for the specified value using the binary search algorithm. The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

As you can see above a binarySearch requires the array to be sorted before you can search it as using the Arrays.sort method.

Here is a simple example using Collections.

    public static void main(String[] args) {
        final List<Integer> integers = new ArrayList<Integer>();
 
        integers.add(10);
        integers.add(9);
        integers.add(11);
 
        Collections.sort(integers, Collections.reverseOrder());
 
        System.out.println(integers);
 
        System.out.println(Collections.binarySearch(integers, 10, Collections.reverseOrder()));
    }

// Json

Ah yes - sorry my writeup in original post was bad.

I need to do Binary Insert Sorting.

Which - I fully realized I've done wrong and going to rewrite my add method.


Basically the array starts out empty (thus sorted?)

i've been misunderstanding the concept - so going to redo it and see if i can get it off the ground.

But basically - my issue was with binary Insert Sorting.

Not able to use any other means of sorting i believe.

So I take it you have to implement the whole sorting your self then, so you cant just use a simple Treeset to do it for you?

    public static void main(String[] args) {
        final TreeSet<Integer> integers = new TreeSet<Integer>(Collections.reverseOrder());
 
        integers.add(10);
        integers.add(9);
        integers.add(11);
        integers.add(5);
        integers.add(87);
        integers.add(46);
        integers.add(1);
        integers.add(90);
 
        System.out.println(integers);
    }

// Json