GeeCON Prague 2014*
The moose likes Java in General and the fly likes Searching string in an array. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Java in General
Bookmark "Searching string in an array." Watch "Searching string in an array." New topic
Author

Searching string in an array.

chhota don
Greenhorn

Joined: Mar 03, 2004
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.
Thanks in advance.
Jean-Francois Briere
Ranch Hand

Joined: Mar 03, 2004
Posts: 101
Maybe something like this:
chhota don
Greenhorn

Joined: Mar 03, 2004
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

Joined: Mar 02, 2003
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

Joined: Mar 03, 2004
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

Joined: Jan 30, 2000
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.


"I'm not back." - Bill Harding, Twister
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
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


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
 
GeeCON Prague 2014
 
subject: Searching string in an array.