CODEWITHSUNDEEP
javaalgorithmdata-structures
SuperManEver
SuperManEver

Reputation: 2362

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

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 :

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.

Upvotes: 0

Views: 322

Answers (1)

justmscs
justmscs

Reputation: 756

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++;
}

Upvotes: 1

Related Questions