CODEWITHSUNDEEP
ruby
Chetan Barawkar
Chetan Barawkar

Reputation: 266

Get the closest value of a number from an array

I have an array:

["7", "8", "11", "13", "14"]

I want the closest inferior number to 11 if any (i.e., 8), or if such a number does not exist, then the closest superior number to 11 (i.e., 13).

Upvotes: 6

Views: 10256

Answers (5)

user16452228
user16452228

Reputation:

Here's another approach using a combination of take_while and drop_while:

Assuming the array is already sorted, this only iterates through the array exactly as far as it needs to and no further:

arr.take_while {|x| x.to_i < num}.last || arr.drop_while {|x| x.to_i<=num}.first

And here it is inserted into a defined method for clarity and testing:

arr_1 = ["7", "9", "11", "13", "14"]
arr_2 = ["11", "13", "14"]
arr_3 = ["13", "14"]
arr_4 = ["11"]
arr_5 = []
arr_6 = ["-2", "-1", "11", "12"]

def first_closest(number, sorted_string_array)
  arr = sorted_string_array
  num = number
  arr.take_while {|x| x.to_i < num}.last || arr.drop_while {|x| x.to_i<=num}.first
end

first_closest(11, arr_1)
#=>  9
first_closest(11, arr_2)
#=>  13
first_closest(11, arr_3)
#=>  13
first_closest(11, arr_4)
#=>  nil
first_closest(11, arr_5)
#=>  nil
first_closest(11, arr_6)
#=>  -1

Upvotes: 0

Vishal
Vishal

Reputation: 7361

Try the below shortest method for getting the closest value:

n = 40
a = [20, 30, 45, 50, 56, 60, 64, 80]
a.min_by{|x| (n-x).abs}

Upvotes: 27

Cary Swoveland
Cary Swoveland

Reputation: 110675

The following method, which does not sort the array, has a time-complexity of O(n), n being the size of the array. By contrast, for methods that sort the array as a first step, the time-complexity is at best O(nlog(n)). Ref

To avoid obscuring the central element of the question, I will assume that the array contains integers rather than string representations of integers. I will briefly address this point after presenting the solution.

def closest(arr, target)
  return nil if arr.empty?
  arr.min_by  { |e| e <= target ? [0, target-e] : [1, e-target] }
end

arr = [11, 7, 13, 8, 11, 14]

closest(arr, 12)   #=> 11
closest(arr, 12.5) #=> 11
closest(arr, 11)   #=> 11
closest(arr, 4)    #=>  7
closest(arr, 7)    #=>  7

See Enumerable#min_by.

Note that arrays are ordered by the method Array#<=> (see the document's third paragraph), so, for example,

target = 12
arr.sort_by  { |e| e <= target ? [0, target-e] : [1, e-target] }
  #=> [11, 11, 8, 7, 13, 14]

Because 0 < 1, the four elements that are no larger than target make up the first four elements of the array returned ([11, 11, 8, 7]) and the two elements that are greater than target comprise the last two elements ([13, 14]), both groups being ordered by the "distance" to target. The method does not use sort_by, but it orders the elements of arr the same way.

[0, target-e] and [1, e-target] could replaced by [n1, target-e] and [n2, e-target], where n1 and n2 are any objects for which n1 <=> n2 #=> -1. For example, n1 = -7 and n2 = 42 or n1 = 'a' and n2 = 'b'.

If arr contains strings representations of integers, as in the question, one may either convert the array to an array of integers as a first step or change the method as follows.

def closest(arr, target)
  return nil if arr.empty?
  target_f = target.to_f
  arr.min_by do |e|
    e_f = e.to_f
    e_f <= target_f ? [0, target_f-e_f] : [1, e_f-target_f]
  end
end

Upvotes: 5

Stefan
Stefan

Reputation: 114158

Yet another way to solve this:

a = arr.map(&:to_i).sort      #=> [7, 8, 11, 13, 14]
a.reverse.find { |e| e < 11 } #=> 8
a.find { |e| e > 11 }         #=> 13

Since find returns nil if no object matches, the last two lines can be combined via:

a.reverse.find { |e| e < 11 } || a.find { |e| e > 11 }

Upvotes: 7

sawa
sawa

Reputation: 168091

h = ["7", "8", "11", "13", "14"].map(&:to_i).sort.group_by{|e| e <=> 11}
h[-1].last || h[1].first # => 8

Upvotes: 16

Related Questions