Inserting in to an Ordered Array using Binary Search

Question

The following is what i have so far. The problem is how do i find the insertion spot. I did some hand tracing on paper and what i observed was eventually the lowerbound and upperbound equal and the insertion spot is always a index higher than the index of lower and upper bounds when they are equal.

I know there are many solutions online but i am really trying to understand this on my own since i only learn and remember things when i learn on my own rather than trying to figure out how others came up with a solution.

If someone can guide me it would be great. Also once i get the insertion spot i can do the rest which is moving all the values a index lower to make spot for the insertion value.

   public void insert(long value) {

            int lowerBound = 0;
            int upperBound = nElems - 1;
            int curIn;

            while (true) {
                curIn = (lowerBound + upperBound) / 2;

                if (a[curIn] < value)
                    lowerBound = curIn + 1;
                else
                    upperBound = curIn - 1;

            }

yeah was thinking of putting break after i figure out the insertion spot.. — user1010101
– user1010101, Commented Jul 21, 2014 at 15:27
eventually the lowerbound and upperbound equal Why not add a check to see whether the two are equal, then, before the other checks in the loop? If you know your base case, check for it. :) — Parthian Shot
– Parthian Shot, Commented Jul 21, 2014 at 15:34
Yeah that makes sense, so if they equal am i safe to assume that the insertion spot is 1 index higher than the index where they equal? — user1010101
– user1010101, Commented Jul 21, 2014 at 15:36

thertweck · Accepted Answer · 2014-07-21 16:00:01Z

2

Binary search has to check for three cases inside the loop:

the value searched for is smaller than the current center element
the value searched for is larger than the current center elelemt
the value is equal to the current center element (the search is finished then)

Binary search should abort, when the lowerBound equals the upperBound and the position in question is not equal to the value searched for.

Anyway, the position at which the search ends is the position where you want to insert the value: if the value at that position equals the value you want to insert, it doesn't matter if you insert at this position or after. If it is smaller, you want to insert after this position, if it is larger, you want to insert at this position.

I won't give code, as OP clearly just asked for a hint.

edited Jul 21, 2014 at 16:00

answered Jul 21, 2014 at 15:26

thertweck

1,1208 silver badges24 bronze badges

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

4 Comments

user1010101 Over a year ago

Yeah how do you determine the insertion spot though? because eventually your lower and upper bound range gets small enough where you are down to one index ...

thertweck Over a year ago

Yes, this is what happens in the worst-case. At that point the value at that position could be the same as the one you want to insert, or it is different: If it is smaller, you want to insert after that position, if it is larger, you want to insert before.

user1010101 Over a year ago

So once i have lower and upper bound equal to each other, am i safe to assume that the insertion spot is either higher or lower than that?

thertweck Over a year ago

Yes, it has to be like that because we initially defined that the array is sorted. Of course you can assume this too, when a[curIn] equals the value you want to insert. curIn is then the spot you want to put the value.

Stefano Buora · Accepted Answer · 2014-07-21 15:39:33Z

0

Hope this may help:

public void insert(long value) {
    int lowerBound = 0;
    int upperBound = nElems - 1;
    int curIn;

    while (lowerBound!=upperBound) { //terminating condition - otherwise you will obtain an infinite loop.
        curIn = (lowerBound + upperBound) / 2;
        //take a choice: put your element immediately before a greater element.
        if (a[curIn] <= value) { //also the same value must be managed as more little than the current.
            lowerBound = curIn + 1;
        } else {
            //You cannot skip curIn lowering down the upper limit, curIn should be the position you are looking for.
            upperBound = curIn; // - 1;
        }
    }

    insert_in_list( value, curIn ); //do it as you wish. place the new element in the curIn position
}

answered Jul 21, 2014 at 15:39

Stefano Buora

1,0626 silver badges13 bronze badges

2 Comments

thertweck Over a year ago

This is inefficient. You may stop early when a[curIn] equals the value you want to insert.

Stefano Buora Over a year ago

True in general, but I did the assumption of "put your element immediatley before a greater element". This assumption orders the element with the same values based on the time of the insertion. I don't know in which application that function will be used. I don't know if the time is important or not. To simplify and to be able to provide a useful answer I did the hypothesis.

Collectives™ on Stack Overflow

Inserting in to an Ordered Array using Binary Search

2 Answers 2

4 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related