CODEWITHSUNDEEP
javaalgorithmsearchbinary-search
Sahat Yalkabov
Sahat Yalkabov

Reputation: 33624

How to convert linear search to binary search?

- This is my find() method using Binary Search algorithm:

Here's the original insert() method using linear search. Pretty straightforward, right?

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()

I need to modify the insert() method to use the binary search algorithm of the find() method. Here's what I came up with so far. Obviously there's something wrong with it, but I can't seem to find the problem. It doesn't work at all, i.e. no insertions are performed:

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

    while(true) {
        curIn = (lowerBound + upperBound) / 2;
        if(a[curIn] == value)
            return curIn;
        else if(lowerBound > upperBound)
            return nElems;
        else {
            if(a[curIn] < value)
                lowerBound = curIn + 1;
            else
                upperBound = curIn - 1;
        }

        for(int k=nElems; k>curIn; k--) // move bigger one up
            a[k] = a[k-1];
        a[curIn] = value; 
        nElems++; 
    }
}

Language: Java

Using ordered array.

Upvotes: 0

Views: 1935

Answers (4)

Jimmy Haxx
Jimmy Haxx

Reputation: 1

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


int pos = 0;

if(value < a[0])
 pos=0;
else if(nElems>0 && value>a[upperBound])
 pos=nElems;
else
{
 while(nElems>1)
 {
  int j = (lowerBound + upperBound ) / 2;

  if(upperBound - lowerBound ==0)
  {
   pos = lowerBound+1;
   break;              // found it
      }
  else if(upperBound - lowerBound ==1)
  {
   pos=upperBound;  //lo encontre
   break;
  }
  else                          // divide range
          {
           if(a[j] < value)
               lowerBound = j + 1; // it's in upper half
       else
           upperBound = j - 1; // it's in lower half
      }  // end else divide range
 }
}


 for(int k=nElems; k>pos; k--)    // move higher ones up
    a[k] = a[k-1];
 a[pos] = value;                  // insert it
     nElems++;                      // increment size

Upvotes: 0

Jeff Meatball Yang
Jeff Meatball Yang

Reputation: 39017

Um, why not just CALL your find function?

public int insertBS(long value) {
    int curIn = find(value); // find where it goes (binary search)
    for(int k=nElems; k>curIn; k--) // move bigger one up
        a[k] = a[k-1];
    a[j] = value; // insert it
    nElems++; // increment size

}

This way, when you optimize/change your find function, your insert function will go faster, too!

As a side note, I think your find function will not give you expected behavior, as written. If you have a list of [0,1,4,5,9] and I search for 7, I will get an index of nElems (5), which could be misinterpreted as the values at indexes 0 to 4 are all less than 7. Seems a little wonky.

Upvotes: 2

Michael Petito
Michael Petito

Reputation: 13161

You need to perform the binary search to find the insertion index before moving elements. In your last code snippet, you are attempting to use the variable curIn to move elements inside your while loop before your binary search has finished. Try moving the for loop outside of the while loop.

Upvotes: 2

Lie Ryan
Lie Ryan

Reputation: 64827

well, it's obvious why the value isn't inserted, it's because you never inserted the value. Once you found the index of the position to insert you simply return from the function without doing anything.

Upvotes: 5

Related Questions