How to find a place where to insert value into ordered array using binary search?

Question

I am doing programming project from book about data structures and algorithms and I need to implement insertion into ordered array using binary search.

My initial implementation for this using linear approach is:

public void insert(long value) {      // put element into array
    int j;
    for (j = 0; j < nElems; j++)      // find where it goes
        if (a[j] > value)             // (linear search)
            break;
    for (int k = nElems; k > j; k--)  // move bigger ones up
        a[k] = a[k-1];
    a[j] = value;                     // insert it
    nElems++;                         // increment size
}  // end insert()

But, I am stuck when I tried to create something similar using binary search approach. Here is what I did:

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

    while(lowerBound < upperBound) {

        curIn = (lowerBound + upperBound) / 2;

        if(arr[curIn]>value && arr[curIn-1] < value) {
            for(int k=nElems; k>curIn; k--) 
                arr[k] = arr[k-1];
            arr[curIn] = value;
        } else {
            if(arr[curIn] > value)
                upperBound = curIn-1;
            else
                lowerBound = curIn+1;
        }
    }   
}  // end insert()

I think my main mistake is the following :

I don't have any logic which handles empty array case.

Give me some advice please. I just started to learn this stuff about a week ago, so some explanation would be great.

Thank you in advance, Nick.

I have an empty array at the result. It should be filled by my values, but it doesn't — SuperManEver
– SuperManEver, Commented Dec 15, 2014 at 9:09
Since you have to shift all the elements after the one inserted anyway, using binary search does not seem to have much benefit here. Sure, you have O(logn) instead of O(n) for searchling, but you still need O(n) for shifting the other elements, so overall complexity stays at O(n). — tobias_k
– tobias_k, Commented Dec 15, 2014 at 9:39
Useful series of articles on binary search on Dr Dobbs drdobbs.com/author/Andrew-Koenig — Jackson
– Jackson, Commented Dec 15, 2014 at 11:12

justmscs · Accepted Answer · 2014-12-16 02:40:33Z

1

During the loop you can keep a loop invariant(insert position always in interval [lowerBound upperBound]).

So when arr[curIn] > value, halve the interval to [lowerBound curIn]

when arr[curIn] <= value, halve the interval to [curIn+1 upperBound]

After the loop, lowerBound is the position to insert.

//Assume arr, nElems are declared somewhere else and enough space to insert...
public void insert(long value) {
    int lowerBound = 0;
    int upperBound = nElems;
    int curIn;
    while(lowerBound < upperBound) {
        curIn = (lowerBound+upperBpund)/2;
        if(arr[curIn] > value) {
            upperBound = curIn;
        } else {
            lowerBound = curIn+1;
        }
    }
    //note lowerBound may equal nElems, it works anyway
    for(int k = nElems; k > lowerBound; k--) {
        arr[k] = arr[k-1];
    }
    arr[lowerBound] = value;
    nElems++;
}

edited Dec 16, 2014 at 2:40

answered Dec 15, 2014 at 9:37

justmscs

7564 silver badges13 bronze badges

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

1 Comment

hk6279 Over a year ago

Two adjustment is required. 1. update nElems after insert 2. initiate upperBound with nElems, not nElems-1

Collectives™ on Stack Overflow

How to find a place where to insert value into ordered array using binary search?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related