CODEWITHSUNDEEP
javaalgorithmbinary-search
user1010101
user1010101

Reputation: 1658

Inserting in to an Ordered Array using Binary Search

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;

            }

Upvotes: 0

Views: 935

Answers (2)

thertweck
thertweck

Reputation: 1120

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

  1. the value searched for is smaller than the current center element
  2. the value searched for is larger than the current center elelemt
  3. 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.

Upvotes: 2

Stefano Buora
Stefano Buora

Reputation: 1062

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
}

Upvotes: 0

Related Questions