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.

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

posted

0

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.

[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.

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