• Post Reply Bookmark Topic Watch Topic
  • New Topic

Binary search on an array of Strings

 
Nikki Smith
Ranch Hand
Posts: 44
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have to use an array for this, however I can use a few different search algorithms to accomplish the same goal. Sequential search would be doable, but that wouldn't be much of a challenge/fun and the array is already in alphabetical order. This almost works, except some state values won't work and the default XX value is returned instead. I'm not sure why. I added some print statements and tried to track down the issue, but am still confused as to why this isn't working. Some of the states that won't work are as follows: AK (index 1), AR (index 3), IN (index 12), IL (index 13), NJ (index 29), NY (index 31), WV (index 47). When I pass those values in it returns the default XX, but yet it works for other states and returns the correct two letter abbreviation. This search uses a pre-filled array of strings containing all 50 states using their 2 letter abbreviations. The first position starts at index 0 and the last is at 49.

 
somashaker goud
Ranch Hand
Posts: 48
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can you check your while condition.



It will be get satisfied in first iteration and in second it will get fail and as per your logic after your loop it will print XX
 
Nikki Smith
Ranch Hand
Posts: 44
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
somashaker goud wrote:Can you check your while condition.



It will be get satisfied in first iteration and in second it will get fail and as per your logic after your loop it will print XX


I've already tried altering the loop.
It's not failing all of the time. In fact, it works with most of the states and will print them as it should, it's only certain states that are returning the default "XX" value.
 
Paul Clapham
Sheriff
Posts: 21975
36
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, line 18 is the only one which sets the "position" variable. So what does that mean? It means that line 18 is never executed in those cases. And why is that? It isn't obvious to me (and certainly not obvious to you either). I'd suggest you get out a pencil and paper and run though the loop manually, writing down what happens to first, last, and middle each time through the loop.
 
Paul Clapham
Sheriff
Posts: 21975
36
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nikki Smith wrote:AK (index 1), AR (index 3), IN (index 12), IL (index 13), NJ (index 29), NY (index 31), WV (index 47).


I thought you said the list was in alphabetical order?
 
Nikki Smith
Ranch Hand
Posts: 44
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's the array I'm using:


If I run the commented out prints at the start of the loop on AR this is the result:

position-1
first0
middle24
MO
last49
Before

position-1
first0
middle11
ID
last23
Before

position-1
first0
middle5
CO
last10
Before

position-1
first0
middle2
AZ
last4
Before

position-1
first0
middle0
AL
last1
Before

position-1
first1
middle1
AK
last1
Before



But if I run it on WA

position-1
first0
middle24
MO
last49
Before

position-1
first25
middle37
PA
last49
Before

position-1
first38
middle43
UT
last49
Before

position-1
first44
middle46
WA
last49
Before


It's a binary search. Position doesn't need to be set each time because it only updates if the string is found in the array which should terminate the loop as well since the first condition is no longer true. At that point it wont be -1 anymore. With each iteration the area it searches is cut in half which is why the first and last indexes are changed each time and the middle is searched to see if it's higher or lower than to determine what half to chop off next and what to limit the first and last indexes to for the next iteration.
 
Nikki Smith
Ranch Hand
Posts: 44
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:
Nikki Smith wrote:AK (index 1), AR (index 3), IN (index 12), IL (index 13), NJ (index 29), NY (index 31), WV (index 47).


I thought you said the list was in alphabetical order?


It is in alphabetical order. Those are the states that aren't working. Some of them will work correctly and will display the two letter abbreviation. Some will not and will show XX. Those listed are some of the ones that will not work correctly.
 
Junilu Lacar
Marshal
Posts: 10409
125
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nikki Smith wrote:Here's the array I'm using:


...
It's a binary search.

A binary search will only work if your array is sorted alphabetically. Those elements are not in alphabetical order. For example, AK should be before AL, AR before AZ, IA before IN, MA before MD, MD before ME, and a few others.
 
Nikki Smith
Ranch Hand
Posts: 44
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:
Nikki Smith wrote:Here's the array I'm using:


...
It's a binary search.

A binary search will only work if your array is sorted alphabetically. Those elements are not in alphabetical order. For example, AK should be before AL, AR before AZ, IA before IN, MA before MD, MD before ME, and a few others.


And now I just wanna go sit in the corner and cry for a while. I was thinking they were in alphabetical order because based on the full name of the state, they are. Didn't even consider a different arrangement for the abbreviated forms.
 
Gravity is a harsh mistress. But this tiny ad is pretty easy to deal with:
the new thread boost feature: great for the advertiser and smooth for the coderanch user
https://coderanch.com/t/674455/Thread-Boost-feature
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!