Practicing inserting data into an array by using binary search, few problems

Question

I'm trying to create a method which inserts and then sort elements in form of binary form.

The problem I am experiencing that my code doesn't insert data correctly which means that output does not appear to be in order at all.

The list is not organized, and data is added in order that is being inserted.

Now, 2 questions, what am I doing wrong here? And how to fix this?

public void insertBinarySearch(long value) // put element into array
{       
    int j = 0;
    int lower = 0;
    int upper = elems-1;
    int cur = 0;

    while (cur < elems)
    {
        cur = (lower + upper ) / 2;

        if(a[cur] < value)
        {
            j = cur + 1;
            break;
        }
        else if(a[cur] > value)
        {
            j = cur;
            break;
        }
        else
        {
            if(a[cur] < value)
                lower = cur + 1;
            else
                upper = cur - 1;
        }
    }

    for(int k = elems; k > j; k--)
        a[k] = a[k-1];

    a[j] = value;

    elems++;
}

If you're adding a lot of elements and then traversing it'd be better to just add the items and sort later as needed. This looks like it involves a lot of shifting. — Eric Pauley
– Eric Pauley, Commented Sep 30, 2012 at 3:27
I would not agree on this. Since we can do organize elements first, then we don't need to create additional loop which would add more computation time to this method (what if that loop had millions of elements). As I was explained in class, doing this way I am doing would save time and processing consumption. — HelpNeeder
– HelpNeeder, Commented Sep 30, 2012 at 3:30

Sidharth Mudgal · Accepted Answer · 2012-09-30 03:25:09Z

3

while (lower <= upper)
{
    curIn = (lower + upper ) / 2;

        if(a[curIn] < value)
            lower = cur + 1;
        else if(a[curIn] > value)
            upper = cur - 1;
        else if (a[curIn] == value)
            break;
}
if(a[curIn] <= value)
    j = curIn + 1;
else j = curIn;

should work.

answered Sep 30, 2012 at 3:25

Sidharth Mudgal

4,26422 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

HelpNeeder Over a year ago

This work very well except one thing. It inserts extra 0 value to the begging of array.

Sidharth Mudgal Over a year ago

This simply finds the position to insert it. How does it insert the extra zero?

HelpNeeder Over a year ago

I'm not sure, really. I will figure this out though. Thanks again for help!

HelpNeeder Over a year ago

Ok, I figured it out, just by checking if number of elements is not 0 will not enter 0 value as fist value to the array. :)

HelpNeeder · Accepted Answer · 2015-04-12 01:44:02Z

Dude, you almost got it, just debug the code and find some missing statement (if's). If you find those missing statements, you code looks better than mine. Don't look mine, you are there, very close.

Let me know for any mistakes and discrepancies etc. Happy coding!!

public class Insertion {
    private int[] a;
    int n;
    int c;

    public Insertion()
    {
        a = new int[10];
        n=0;
    }

    int find(int key)
    {
        int lowerbound = 0;
        int upperbound = n-1;

        while(true)
        {
            c = (lowerbound + upperbound)/2;
            if(n==0)
                return 0;
            if(lowerbound>=upperbound)
            {
                if(a[c]<key)
                    return c++;
                else
                    return c;
            }
            if(a[c]>key && a[c-1]<key)
                return c;
            else if (a[c]<key && a[c+1]>key)
                return c++;
            else
            {
                if(a[c]>key)
                    upperbound = c-1;
                else
                    lowerbound = c+1;
            }
        }
    }

    void insert(int key)
    {
       find(key);
       for(int k=n;k>c;k--)
       {
           a[k]=a[k-1];
       }
       a[c]=key;
       n++;
    }
    void display()
    {
        for(int i=0;i<10;i++)
        {
            System.out.println(a[i]);
        }
    }

    public static void main(String[] args)
    {
        Insertion i=new Insertion();
        i.insert(56);
        i.insert(1);
        i.insert(78);
        i.insert(3);
        i.insert(4);
        i.insert(200);
        i.insert(6);
        i.insert(7);
        i.insert(1000);
        i.insert(9);
        i.display();
    }
}

Kenogu Labz · Accepted Answer · 2012-09-30 03:32:57Z

0

If you're trying to insert an item into an unsorted list, you can't expect the list to be sorted if you don't directly sort it afterwards.

Binary search can only be used on a sorted list. Your results mean nothing otherwise: after all, if you're searching for an element - let's use 8 for example - how do you know if an item belongs before or after 8?

[ 1 2 3 4 5 6 7 8 9 10 11 ]

Notice that, if I find 8, I know that everything after it is greater than 8, and everything before is less than 8. But what about this list?

[ 1 4 11 9 8 6 7 2 5 3 10 ]

Yikes! Now, looking at 8, you can see that the position of 8 no longer has anything to do with the items that are less than or greater than 8. Trying to find an element with binary search in this list will give you incorrect information, whether it finds the item you're looking for or not.

To get this working, make sure the list is always sorted (which should be the case if you always insert items into the correct position in the list), or to sort it before inserting new elements. Binary search will serve you just fine then.

answered Sep 30, 2012 at 3:32

Kenogu Labz

1,1341 gold badge10 silver badges20 bronze badges

2 Comments

HelpNeeder Over a year ago

I am searching for a location where number is higher than previous number and lower than next number then by using this place I am moving the array entries that are after the field by one which will give me empty space where I can insert my value. The point of this code is to insert the items after indexing items.

Kenogu Labz Over a year ago

So the list is sorted before this method is called? I was running with the assumption it wasn't, since you said 'The list is not organized'. Sorry for the confusion.

Collectives™ on Stack Overflow

Practicing inserting data into an array by using binary search, few problems

3 Answers 3

4 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related