• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Searching string in an array.

 
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 101
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Maybe something like this:
 
chhota don
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 233
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[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.
 
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic