CODEWITHSUNDEEP
algorithmdata-structurestime-complexity
Hossein Mobasher
Hossein Mobasher

Reputation: 4472

Nearest number to set of numbers

Suppose that we have a set of number as P = { p1, p2, p3, ..., pn } ( length(P) = n ) and choose a number as q. So I want to find an algorithm to get the nearest member of set P to q. So the question is: What structure is appropriate to keep data ( p1, p2, ... ) and algorithms to find nearest member of P to q in O(1) time complexity.

Upvotes: 2

Views: 1259

Answers (2)

ypercubeᵀᴹ
ypercubeᵀᴹ

Reputation: 115520

The only way I can think of getting O(1) time complexity is if you can use O(pn) space and O(pn) time to preorder P and allocate values in a pn size array.

Preorder P so p1 is the minimum and pn is the maximum (I assume that they are integers.) Then store in an array with size (pn-p1+1) the values:

A(p1) = p1
for  i = 2  to  n
    for  q = p(i-1)+1  to  (p(i-1)+p(i))/2
        A(q) = p(i-1)
    for  q = (p(i-1)+p(i))/2  to  p(i) 
        A(q) = p(i)

Then all you have to check for a certain q is:

if q < A(p1)
    closest = A(p1)
elif q > A(pn)
    closest = A(pn)
else
    closest = A(q)

Upvotes: 1

zvrba
zvrba

Reputation: 24546

  1. You cannot get O(1) complexity. The closest you can get to that is O(lg lg n) by using a van Emde Boas tree.
  2. If the set is static, use a sorted vector and binary search (O(lg n)) to find the nearest element.
  3. If the set can change between queries, use an appropriate data structure for maintaining dynamic sets (e.g., AVL or red-black tree).

Upvotes: 6

Related Questions