• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Binary search in sorted array of strings

 
Luke Stamper
Ranch Hand
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1776
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1776
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10527
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Luke Stamper
Ranch Hand
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10527
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I understand why the first one works now. Thanks Winston.

Still working on the faster alternative....
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic