Question

How would I make this BinarySearch method recursive?

________________________________________________

protected void runBinarySearch(Person target, List<Person> list) {

int firstIndex = 0;

int lastIndex = list.size()-1;

while(firstIndex <= lastIndex) {

int mid = (firstIndex+lastIndex)/2;

if(list.get(mid).equals(target)) {

paint(mid, STYLE_FOUND);

delay();

delay();

paint(mid, STYLE_FOUND);

return;

}

else if(target.compareTo(list.get(mid))>0) {

firstIndex = mid+1;

paint(mid, STYLE_MISMATCH);

delay();

delay();

paint(mid, STYLE_NOT_FOUND);

}

else{

lastIndex = mid-1;

paint(mid, STYLE_MISMATCH);

delay();

delay();

paint(mid, STYLE_NOT_FOUND);

}

}

System.err.println("Binary Search stub unimplemented.");

}

_________________________________________________

This method just highlights a value when it is a match to the target and it highlights another value when it is not.

Answer 1

CODE

protected void runBinarySearch(Person target, List<Person> list, int firstIndex, int lastIndex) {

if (lastIndex >= firstIndex) {

int mid = (firstIndex+lastIndex)/2;

if(list.get(mid).equals(target)) {

paint(mid, STYLE_FOUND);

delay();

delay();

paint(mid, STYLE_FOUND);

return;

}

else if(target.compareTo(list.get(mid))>0) {

runBinarySearch(target, list, mid + 1, lastIndex);

paint(mid, STYLE_MISMATCH);

delay();

delay();

paint(mid, STYLE_NOT_FOUND);

}

else {

runBinarySearch(target, list, firstIndex, mid - 1);

paint(mid, STYLE_MISMATCH);

delay();

delay();

paint(mid, STYLE_NOT_FOUND);

}

}

}