Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Trouble with Binary Search on Insert Method

  1. #1
    Junior Member
    Join Date
    Feb 2010
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,372
    Thanks
    183
    Thanked 836 Times in 779 Posts
    Blog Entries
    5

    Default Re: Trouble with Binary Search on Insert Method

    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.

Similar Threads

  1. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 09:27 AM
  2. Binary Search Tree implementation
    By Ceasar in forum Java Theory & Questions
    Replies: 3
    Last Post: October 9th, 2009, 01:23 AM
  3. Having trouble insert/sorting array values w/ binary searching.
    By bh-chobo in forum Collections and Generics
    Replies: 4
    Last Post: October 8th, 2009, 03:38 AM
  4. Input file parsing to insert into DB
    By IDForums in forum File I/O & Other I/O Streams
    Replies: 3
    Last Post: September 30th, 2009, 03:29 AM
  5. Insert sort algorithm
    By Alysosh in forum Algorithms & Recursion
    Replies: 1
    Last Post: May 26th, 2009, 10:28 AM