Thread: Trouble with Binary Search on Insert Method

Alright so the task at hand is to add to the existing program OrdArray an insert method that uses a binary search. And currently I am having a disaster of a time trying to get the program to add elements into the correct place.

I will definitely admit my code is a mess. From attempting to debug it really seems that at random the temp place holder variable will have a value (Ex. 99), but by the next line where that value is to be inputted into the array the temp variable inputs a 0.

public class OrdArray {
    private long[] a;
    private int nElms;
 
    public OrdArray(int Max)
    {
        a = new long[Max];
        nElms = 0;
    }
 
public void insert (long value)
    {
            long temp = 0, temp2 = 0;
            int curIn;
            int lowerBound = 0;
            int upperBound = nElms - 1;
 
            boolean skip = true;        //boolean to skip binary search for first two inserted values
 
         if((nElms-1) == a.length)      //can an element be added
            System.out.print("The array is full and can not insert another element");
 
        else                        //an element can be entered
        {
 
            if(nElms == 0)
            {
                a[0]= value;
                nElms++;
                skip = false;
            }
 
            else if(nElms ==1)      //Insert first two value into array
            {
 
                if(a[0]< value)
                    a[1] = value;
                else
                {
                    temp = a[0];
                    a[0] = value;
 
                }
                skip = false;
                nElms++;
            }//End of insert first two values.
 
 
            if(value < a[0])            //Check insert value against first element in array
            {
                temp = a[0];
                a[0] = value;
                for (int k =lowerBound+1; k < nElms; k++) //move values up array
                    {
                        temp2 = a[k];
                        a[k]  = temp;
                        temp = temp2;
                    }
                    nElms++;
                    a[nElms] = temp;
                    skip = false;
            }
 
            else if(value> a[nElms-1])          //Check insert value against last value in array
            {
                a[nElms] = value;
                nElms++;
            }
 
            while(skip)
            {
                curIn = (lowerBound + upperBound) / 2;  //find midpoint
 
                if(a[lowerBound+1] > value)             //found at what point to enter value from below value
                {
                    temp = a[lowerBound+1];            //hold that current spot's value
                    a[lowerBound + 1] = value;       //put value in that spot
                    for (int k =lowerBound+2; k <= nElms; k++) //move values up array
                    {
                        temp2 = a[k];
                        a[k]  = temp;
                        temp = temp2;
                    }
                    nElms++;                    //Increase number of elements
                    break;
                }
 
                if(a[upperBound -1] < value)             //found at what point to enter value from above value
                {
                    temp = a[upperBound];            //hold that current spot's value
                    a[upperBound] = value;       //put value in that spot
                    for (int k =upperBound+1; k <= nElms; k++) //move values up array
                    {
                        temp2 = a[k+1];
                        a[k]  = temp;
                        temp = temp2;
                    }
                    nElms++;                    //Increase number of elements
                    break;
                }
 
                else if(a[curIn] < value)   //where is it in the array
                    lowerBound = curIn +1;  //it's in upper half
                else
                    upperBound = curIn-1;   //it's in lower half
            }//end while
        }//end else
    }//end insert()
}

This is what I am suppose to test.

public class OrderedApp {
 
    public static void main(String[] args)
    {
        int maxSize = 100;
        OrdArray arr;               //create new ordered array
        arr = new OrdArray(maxSize);    //initialize ordered arry
 
        arr.insert(77);             //Insert values
        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);
    }

As of right now the output is

0 11 22 44 55 77 0 88 0 66 0 33 0 0

So the sort partially works and then doesn't sort some numbers or overwrites them.

Check your placement of nElms++ versus your access to your array using nElms. As a side note I'm not entirely sure why you wish to do a binary search and array re-organization for every insert as opposed to using a binary tree or sorting the array post insertions, but I assume you have your reasons.