iloveprogramming iloveprogramming - 1 year ago 65
Java Question

Binary search for an array of strings

I am wondering why my binary search is returning a different value than my linear search is. Can someone explain to me what I am doing wrong? Should I be returning something different?

public class BinarySearch extends SearchAlgorithm
{
public int search (String [] words, String wordToFind) throws ItemNotFoundException {
int lowIndex = 0;
int highIndex = words.length - 1;
while (lowIndex <= highIndex) {
int midIndex = (lowIndex + highIndex) / 2;
if ((words[midIndex]).equals(wordToFind)) {
return midIndex;
}
if (wordToFind.compareTo(words[midIndex]) > 0) { //wordToFind > midIndex
lowIndex = midIndex + 1;
}
if (wordToFind.compareTo(words[midIndex]) < 0) { //wordToFind < midIndex
highIndex = midIndex - 1;
}
lowIndex++;
}
return -1;
}


}

Here is what it returns. The first group is with the linear search and the 2nd is with the binary.

DISCIPLINES found at index: 11780 taking 0 comparisons.
TRANSURANIUM found at index: 43920 taking 0 comparisons.
HEURISTICALLY found at index: 18385 taking 0 comparisons.
FOO found at index: -1 taking 0 comparisons.

DISCIPLINES found at index: 11780 taking 0 comparisons.
TRANSURANIUM found at index: 43920 taking 0 comparisons.
HEURISTICALLY found at index: -1 taking 0 comparisons.
FOO found at index: -1 taking 0 comparisons.

Answer Source

Try changing your logic to :

int midIndex = (lowIndex + highIndex) / 2;
while (lowIndex <= highIndex) {    
    if ((words[midIndex]).equals(wordToFind)) { //use equals
        return midIndex;
    }
    if (wordToFind.compareTo(words[midIndex]) > 0) { //wordToFind > midIndex
        lowIndex = midIndex + 1;
    }
    if (wordToFind.compareTo(words[midIndex]) < 0) { //wordToFind < midIndex
        highIndex = midIndex - 1;
    }
// getting rid of infinite loop when the value is not in the list
    if (lowIndex==highIndex && !wordToFind.compareTo(words[midIndex]) {
        return -1;
    }
    midIndex = (lowIndex + highIndex) / 2; // notice removing lowindex++
}

The lowIndex++ inside the while was not required since that was updating the lowIndex irrespective of the BS algorithn updating the indexes based on the comparison with midIndex value.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download