how to search in O(1)

general
1

I want to search an element in an integer array in O(1), what is the best way to do it, and values of elements are greater than array size. thank you.

2

Use hash (HashSet) if you only insert, remove and check if set contains a distinct value.

3

Else specify the details of your requirements, like functions to be performed and required time complexity, Number of elements.

4

If you use c++ then the alternative would be to use std::unordered_map it is internally implemented as Hash Table and hence gives you an O(1) search time in average case. Refer this and this for more details.

5

is it for java or c++

6

Oops…

I typically use java, so HashSet came to my mind.

unordered map in c++ is same as HashSet in java will give O(1) amortised time complexity, while ordered map give O(logN) time complexity.

1 Like
7

If your data points are from a set of discrete values (such as integers from 1 to 1,000,000) you can keep an array of the count of each possible value. This is simpler than a hash table and doesn’t need rehashing or collision detection, but uses more memory.