iloveprogramming iloveprogramming - 20 days ago 5
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

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.

Comments