File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Binary search in sorted array of strings Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Binary search in sorted array of strings" Watch "Binary search in sorted array of strings" New topic
Author

Binary search in sorted array of strings

Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
My code is working well except that I can't figure out a good way to print out different string values at different array locations. Here is the sample output...


Example Output:

--------------------Configuration: <Default>--------------------
Integer test array contains:
0 2 4 6 8 10 12 14 16 18
-3 is not in the array.
-2 is not in the array.
-1 is not in the array.
0 is at index 0
1 is not in the array.
2 is at index 1
3 is not in the array.
4 is at index 2
String test array contains:
apples oranges peaches strawberries watermelons
apples is at index 0
plums is not in the array.

Process completed.


I have my string array sorted, but I can't figure out how to print what is at index 0 or how to see if something isn't in the array. Please help. I've done research all night, but haven't been able to figure it out. My issue (i think) is between lines 40-47.


John Jai
Bartender

Joined: May 31, 2011
Posts: 1776
I get a compilation error in the below line of code.

You try to call a searchString() method with parameters String[], String with an incorrect argument list of String[], int.

Check the line #43 in the given code.
John Jai
Bartender

Joined: May 31, 2011
Posts: 1776
You can add the fruits you need to search in a String array and check for them in the search() method. The mistake you have previously made is sending an int where a String was expected.





Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

Luke Stamper wrote:I have my string array sorted, but I can't figure out how to print what is at index 0 or how to see if something isn't in the array. Please help. I've done research all night, but haven't been able to figure it out. My issue (i think) is between lines 40-47.

Actually I think it's between lines 86 and 101. You have a working search() method starting at line 59 (at least I presume it works), and yet you've written your searchString() method completely differently. Why?

Winston

PS: You also have a subtle error in your midpoint calculation (and don't worry, many before you have made the same mistake; including experts).
A teaser for you: The correct way to calculate a midpoint (assuming first and last are indexes) is:
int mid = first + ((last - first) / 2);
Why?

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
Thanks everyone for your help. It is truly appreciated.

Winston...I was confused on how writing search methods for ints and strings. I was doing research and found one that I thought would work, but I don't think I fully understood how it worked. Also, the midpoint formula you posted...is it correct because it accounts for negative numbers?

Thanks again everyone!
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

Luke Stamper wrote:Winston...I was confused on how writing search methods for ints and strings. I was doing research and found one that I thought would work, but I don't think I fully understood how it worked.

Ah, I did wonder. Do you understand how the first one works now?

Luke Stamper wrote:Also, the midpoint formula you posted...is it correct because it accounts for negative numbers?

Sort of, although indexes can't be negative. The problem is that your formula can cause a numeric overflow if you have values for first and last that add up to more than Integer.MAX_VALUE. That will result in a negative number which remains negative after the division and eventually leads to an ArrayIndexOutOfBoundsException. Obviously, the values have to be huge in order for it to happen, which is why the problem can (and did) go undiscovered for a long time. The second formula prevents that from happening.

BTW: A faster alternative in Java is:
int mid = (first + last) >>> 1;
I'll leave you to work out why.

Winston
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
I understand why the first one works now. Thanks Winston.

Still working on the faster alternative....
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Binary search in sorted array of strings