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.
``````

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