Binary Search Help

[Snario]

I have a file that is as such:

1
string1
2
string2
4
string3
6
string4
...
100
string 21

Where the numbers are ordered but aren't related to each other any other way.

I'm trying to write a recursive Binary Search method that will return with "The book wasn't found" or the string associated with an inputted reference number.

e.g.,
Input = 4
Output = string3

Input = 3
Output = "The book wasn't found"

Here's my code (It doesn't work for 2, 4, 6, or 100, but for every other number it does work.)

code:

public static String binarySearch(String[] A, int left, int right, String V) {         int middle;         if (left > right) {             return "The book was not found.";         }         middle = (left + right) / 2 ;         if (middle % 2 != 0) {             middle--;         }         int compare = V.compareTo(A[middle]);         if (compare == 0) {             return A[middle + 1];         }         if (compare < 0) {             return binarySearch(A, left, middle - 2, V);         } else {             return binarySearch(A, middle + 2, right, V);         }     }

[Zren]

... Why not just load the file contents into a Map?

[Snario]

I don't know what that means, I'm still learning Java and I'm trying to do this with a Binary Search method like the one I posted. I'll learn what a Map is now though, however I'd still like this done the (presumably) less efficient way.

[Zren]

All right. If we need to stick to just data structures you know, then why not use two arrays? One for the odd rows, and one for the even rows.

nums[0] = row 0 (parsed as an integer)
data[0] = row 1
nums[1] = row 2 (parsed as an integer)
data[1] = row 3
...

That way, you can binary search the first array for the index. If it's valid, use the index for the second array.

[Snario]

I've done that, but for some reason the binary search just will not work with 2, 4, 6, and 100. Here's the code for that:

http://pastebin.com/iy6Eu04Y

[Insectoid]

Quote:

the binary search just will not work with 2, 4, 6, and 100.

What do you notice about those numbers?

[Snario]

They're even and they are (almost) the extremes of both the highest number and lowest number. However, 94 works if I add it to the file and so does 96, 98 does not work.

[Zren]

Try debugging by printing each call to your recursive method and display what the values of the relevant parameters are.

Eg (put right at the start of the function):

Java:

System.out.format("binarySearch(left=%d, right=%d)%n", left, right);

[Snario]

Thanks Zren, I didn't know you could do that. The problem was that I was comparing strings and expecting them to act like integers.