CODEWITHSUNDEEP
pythonfunction
Josh Ortega
Josh Ortega

Reputation: 179

Finding the closest number equal to or greater than a given number

I have a python function in which I need to find the number in a list 'values' that's closest to a give number 'n' but that's greater than or equal to 'n'.

So far I have this:

def nearest_largest_value2 (n, values):
      closest = []
      for i in values:
        if i == n:
          closest = i
        elif (i > n) and (i-n < 2):
          closest = i
       return closest

print(nearest_largest_value2(5, [1,3,4,6,7]))
print(nearest_largest_value2(5, [7,6,4,3,1]))
print(nearest_largest_value2(5, [1,3,4,5,6,7]))

Problem is that I'm getting the answer I want for the first two print statements (6) but I'm getting '6' for the last print statement when I want to get 5.

I'm new to Python but I thought once the first if clause was satisfied the code would stop.

Upvotes: 1

Views: 2917

Answers (2)

sharhp
sharhp

Reputation: 418

If you have multiple queries with different numbers, but to the same list, then it's more efficient to first sort the list and then do a binary search on it.

from bisect import bisect_left

values = [7, 6, 4, 3, 1]

values.sort()

def nearest_largest_value2 (n, values):
    try:
        result = values [bisect_left (values, n)]
    except IndexError: # when number is > every element of list 
        result = None
    return result

print (nearest_largest_value2 (5, values)) # 6
print (nearest_largest_value2 (3, values)) # 3
print (nearest_largest_value2 (8, values)) # None

Let p correspond to length of 'values' list and q correspond to the number of inputs 'n' (or # times nearest_largest_value2 is invoked).

In the stated case, Time Complexity of the previous solution is O(pq) whereas Time Complexity of the current solution is O((p + q)logp).

Upvotes: 0

Mureinik
Mureinik

Reputation: 312219

The condition i-n < 2 is wrong. Instead, you should be checking if the current i is closer than the current closest. E.g.:

def nearest_largest_value2 (n, values):
  closest = None
  for i in values:
    if (i >= n) and (closest is None or i < closest):
      closest = i
  return closest

EDIT:
 An alternative way to describe the problem is to find the minimal value that's larger or equal than n. Describing the problem like that allows for a more "pythonic" oneliner:

def nearest_largest_value2 (n, values):
    return min(v for v in values if v >= n)

EDIT2:
 As @ekhumoro pointed out, the alternative solution presented in the previous edit will break if values does not contain any element that is equal to or greater than n. He also graciously offered a fix for it:

def nearest_largest_value2 (n, values):
    min([v for v in values if v >= n] or [None])

Upvotes: 2

Related Questions