Win a copy of TDD for a Shopping Website LiveProject this week in the Testing forum!
  • 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
  • Paul Clapham
  • Ron McLeod
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
  • Frits Walraven
Bartenders:
  • Piet Souris
  • Himai Minh

Data Structure that provides constant search time

 
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have an array of numbers(long).
The complexity of search in a number in this case is O(n).
I am looking for a Data Structure which provides constant search time.
 
Ranch Hand
Posts: 263
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
While you can get searches to run in O(1) in the best case (i.e. already sorted data), the best average case search you can do is O(log n).
Cheers,
[ April 14, 2005: Message edited by: Tom Blough ]
 
author
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Take a look at java.util.HashSet. It actually provide O(1) searches, with good implementations of hashCode().
[ April 14, 2005: Message edited by: Ilja Preuss ]
 
ranger
Posts: 17346
11
Mac IntelliJ IDE Spring
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"Mariya"-
Welcome to the JavaRanch! Please adjust your displayed name to meet the

JavaRanch Naming Policy.

You can change it

here.

Thanks! and welcome to the JavaRanch!

Mark
 
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Tom Blough:
While you can get searches to run in O(1) in the best case (i.e. already sorted data), the best average case search you can do is O(log n).
Cheers,

[ April 14, 2005: Message edited by: Tom Blough ]



This is true only if you are using a list. Other data structures, as Ilja pointed out, can provide O(1) search time. Under the hood, HashSet probably uses a hashtable, which is a fairly common data structure. If you need to implement your own hashtable, then you should google for more information on it. You should also become familiar with the data structures that are already available in the Collections Framework.

Layne
 
Nimmy
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for your responses.


I think my question was not clear.
I need to store primitive types (array of long values).
In collection framework we are using objects.
I don�t want to convert long to an object of wrapper class and save it.
Collection framework provides us that facility to look for a particular value in a better way.

I have a long array and I want to look for a particular value in that array.
Can you suggest me one way to accomplish?
 
Ilja Preuss
author
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
For a search in an array, Tom's response applies - O(log n) is the best you can get. For that, your array needs to be sorted, then you can simply use Arrays.binarySearch.
 
"I know this defies the law of gravity... but I never studied law." -B. Bunny Defiant tiny ad:
Free, earth friendly heat - from the CodeRanch trailboss
https://www.kickstarter.com/projects/paulwheaton/free-heat
reply
    Bookmark Topic Watch Topic
  • New Topic