This week's book giveaway is in the Other Languages forum.We're giving away four copies of Functional Reactive Programming and have Stephen Blackheath and Anthony Jones on-line!See this thread for details.
Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Searching string in an array.

chhota don
Greenhorn
Posts: 6
hi to all,
Can any one tell what would be the better way (performance wise) to search a string in a String array.

Jean-Francois Briere
Ranch Hand
Posts: 101
Maybe something like this:

chhota don
Greenhorn
Posts: 6
hi Jean-Francois Briere,
Thanks for your response. Your code is using linear search algorithm, i want to know about more effiecient way. I have seen one more algorithm that is java.util.Array.binarySearch(Object[], Object), I just want to confirm that, would it better if i use this logic.

Gabriel White
Ranch Hand
Posts: 233
Chhota, I agree with Jean-Francois. Are you looking for a method that will use a runtime of O(1)? Jean-Francois' example uses a the hash method which is very slick and efficient. I'm sure there is a more efficient way, but this one is pretty darn good. The only way this wouldn't be any good is if the string array was extrememly long, thus the O(n) approach would have to be looked over again. And I am also confused by your comment of Jean-Francois' code using a linear search algorithm. This code does not sort from the middle of the string, it spans the entire string. A linear search algo runtime is O(log n) and not O(n).
HTH.
Gabe
[ March 03, 2004: Message edited by: Gabriel White ]
[ March 03, 2004: Message edited by: Gabriel White ]

Jean-Francois Briere
Ranch Hand
Posts: 101
I have seen one more algorithm that is java.util.Array.binarySearch

You did not mention that the String array is already sorted in ascending order according to the natural ordering of its elements.
If this this the case, then of course a binary search is the best solution.
Please next time post a more precise question.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
[Gabriel White]: And I am also confused by your comment of Jean-Francois' code using a linear search algorithm. This code does not sort from the middle of the string, it spans the entire string. A linear search algo runtime is O(log n) and not O(n).

I'm trying to make some sense of this, but I'm not having any luck. Jean-Francois showed a linear search, which is O(n). (n being the number of elements in the array.) A binary search would be O(log(n)). Of course, if the array isn't already sorted then this doesn't help much. However, if you're going to run many saerches of the same array, there's an even better solution:

Using a HashMap this way will take a bit longer to set up initially - but each subsequent search will be O(1). This can be a big savings if n is large and you have lots of searches. For an array of just a few items, it's not worth the trouble - but if you have an array of thousands of items, using a HashMap will make a big difference.

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
Are you married to array? Here's an article about Ternary Search Tree. The sample applet takes minutes to load about 48,000 words, but goes like lightning after that. It's a very fast algorithm for searching while you type or finding all words that start with *
http://www.javaworld.com/javaworld/jw-02-2001/jw-0216-ternary.html