How to convert linear search to binary search?

Question

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

• It works just as you would expect it to. No problems at all.

  public int find(long searchKey) {
  int lowerBound = 0;
  int upperBound = nElems - 1;
  int currentIndex;
  
  
  while(true) {
      currentIndex = (lowerBound + upperBound) / 2;
      if(a[currentIndex] == searchKey)
          return currentIndex; // found it!
      else if(lowerBound > upperBound)
          return nElems; // can't find it
      else { // so then divide range
          if(a[currentIndex] < searchKey)
              lowerBound = currentIndex + 1; // it's in upper half
          else
              upperBound = currentIndex - 1; // it's in lower half
      } // end else divide range
  } // end while loop
  } // end find() method
  

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.