# Find the closest items in an array to a given value

**URL:** <https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661>\
**Category:** Ruby\
**Created:** [October 29, 2007, 9:20pm UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661 "2007-10-29T21:20:24Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 29, 2007, 9:20pm UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/1 "2007-10-29T21:20:24Z")

</div>

Hi!

I’m searching for a light method for finding the closest items to a  
given  
value.

example/

1…10  
in a range  
i give, 5.5, return 5 and 6 for example…

as i’m working with arrays, containing numbers, but with no regular  
step…  
it will change i think.  
example…

a = [1, 1.25, 2, 3, 3.5]

if i give 1.85, it gives me 1.25 and 2

It’s for a little music game, where player has to tap at the right  
moment,  
notes are register in a array, with the correct time, and as players  
can’t  
be accurate as a computer, i need some error margin. I working with  
0.05  
rounded values.

Also, if someone knows a good way to synchro Scrolling and Music with  
tempo  
value that would be great…  
I mean, not the conversion to find how many frames between each beats.  
but  
how to convert, the number of frames between 2 beat to a distance in  
pixel…? ( and possibly with a set-able speed) ?

Thanks.

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 29, 2007, 10:45pm UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/2 "2007-10-29T22:45:53Z")

</div>

On 29.10.2007 21:19, trebor777 wrote:

> it will change i think.  
> example…
> 
> a = [1, 1.25, 2, 3, 3.5]
> 
> if i give 1.85, it gives me 1.25 and 2

It’s crucial to know whether your sequence of values is always sorted.  
If it is, you can use #each\_cons and return the pair where left is  
less-or-equal than x and right is greater-than x.

If not, you can just iterate through the array and remember the last  
match and its distance - overwrite when smaller distance.

robert

PS: A nice task for #inject. 🙂

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 29, 2007, 11:26pm UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/3 "2007-10-29T23:26:13Z")

</div>

2007/10/29, trebor777 [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> i give, 5.5, return 5 and 6 for example…  
> It’s for a little music game, where player has to tap at the right moment,  
> pixel…? ( and possibly with a set-able speed) ?
> 
> Thanks.
> 
> –  
> View this message in context:  
> [http://www.nabble.com/find-the-closest-items-in-an-array-to-a-given-value.-tf4714369.html#a13475984](http://www.nabble.com/find-the-closest-items-in-an-array-to-a-given-value.-tf4714369.html#a13475984)  
> Sent from the ruby-talk mailing list archive at [Nabble.com](http://Nabble.com).

Something like this? (Supposing the array may not be in order)

def array\_between(a=[], v=0.0)  
return [] if a.empty?  
return [v, a.min] if v \< a.min  
return [a.max, v] if v \> a.max  
ret = []  
ret.push a.find {|num| num \< v}  
ret.push a.find {|num| num \> v}  
ret.push v if ret.size \< 2  
return ret.sort  
end

Just a quick 10-second sketch… Maybe you should have tried this too.  
And i know you from other forums too! Nice to see you here trebor!!

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 29, 2007, 11:54pm UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/4 "2007-10-29T23:54:52Z")

</div>

Hi –

On Tue, 30 Oct 2007, Robert K. wrote:

> PS: A nice task for #inject. 🙂

Is that your .sig? 🙂

David

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 29, 2007, 11:51pm UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/5 "2007-10-29T23:51:42Z")

</div>

trebor777 wrote:

> Hi!
> 
> I’m searching for a light method for finding the closest items to a  
> given  
> value.

[1,2,3,4,5,6].min {Â |a,b| (a-value).abs \<=\> (b-value).abs }

Regards  
Stefan

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 30, 2007, 12:25am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/6 "2007-10-30T00:25:53Z")

</div>

Stefan R. wrote:

> trebor777 wrote:
> 
> > Hi!
> > 
> > I’m searching for a light method for finding the closest items to a  
> > given  
> > value.
> 
> [1,2,3,4,5,6].min {Â |a,b| (a-value).abs \<=\> (b-value).abs }
> 
> Regards  
> Stefan

Since you want more than 1 you can either implement your own min method  
that returns the 2 smallest ones, that’d happen in O(n), or you can sort  
by the distance, which is O(nlogn):  
ary.sort\_by { |item| (value-item).abs }.first(n)  
If you just want all values that are a max difference of x from y, you  
can use:  
ary.select { |item| item - x \<= y }

Regards  
Stefan

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 30, 2007, 1:43am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/7 "2007-10-30T01:43:32Z")

</div>

> It’s crucial to know whether your sequence of values is  
> always sorted.

arr = […]  
sorted\_arr = arr.sort

> PS: A nice task for #inject. 🙂

Unfortunately, from tests I have done in other threads, it appears that  
inject is not very efficient, i.e. it’s slow.

Flávio Lisbôa wrote:

> def array\_between(a=[], v=0.0)  
> return [] if a.empty?  
> return [v, a.min] if v \< a.min  
> return [a.max, v] if v \> a.max  
> ret = []  
> ret.push a.find {|num| num \< v}  
> ret.push a.find {|num| num \> v}  
> ret.push v if ret.size \< 2  
> return ret.sort  
> end
> 
> Just a quick 10-second sketch… Maybe you should have tried this too.  
> And i know you from other forums too! Nice to see you here trebor!!

That doesn’t work:

a = [1.1, 1.3, 1.4, 2, 2.2, 3]  
target = 1.85  
p array\_between(a, target)

–output:–  
[1.1, 2]

detect returns the first value for which block isn’t false, which will  
be the first value in the array that is less than the given number. The  
op wants the biggest number in that array that is less than the given  
number, which could be the last number in the array.

> [1,2,3,4,5,6].min { |a,b| (a-value).abs \<=\> (b-value).abs }

That doesn’t work. It returns only the closest single value.

> ary.sort\_by { |item| (value-item).abs }.first(n)

That doesn’t work either. It returns the two closes values, which means  
that both returned values could be less than or greater than the given  
number. The op wants the two closest number that is lower than the  
given number and the closest number that is higher than the given  
number.

The following are two solutions that appear to do what the op wants.  
The first one stores the closest lower value and the closest higher  
value in two variables as it steps through the array:

a = [1.25, 1, 3, 1.9, 1.95, 2.1, 2.2, 1.5]  
target = 1.85

closest\_lower = nil  
closest\_higher = nil

a.each do |elmt|  
if elmt \< target  
if !closest\_lower or elmt \> closest\_lower  
closest\_lower = elmt  
end

elsif elmt \> target  
if !closest\_higher or elmt \< closest\_higher  
closest\_higher = elmt  
end

else #if elmt == target  
#do something  
end  
end

Surprisingly, this is slightly faster–even for very large arrays:

target = 1.85

less\_than = []  
greater\_than = []

a.each do |elmt|  
if elmt \< target  
less\_than \<\< elmt

elsif elmt \> target  
greater\_than \<\< elmt  
end  
end

puts less\_than.max  
puts greater\_than.min

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 30, 2007, 3:19am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/8 "2007-10-30T03:19:24Z")

</div>

Ara.T.Howard-2 wrote:

> > rounded values.
> 
> [“b”, “c”, “c”]  
> [“c”, “c”, “d”]
> 
> ## a @ [http://codeforpeople.com/](http://codeforpeople.com/)
> 
> it is not enough to be compassionate. you must act.  
> h.h. the 14th dalai lama

While waiting for solutions, i did something really similar.

a = myhash.keys.sort[value-0.05…value+0.05]

then i just use

myhash[a[x]]

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 30, 2007, 3:22am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/9 "2007-10-30T03:22:19Z")

</div>

Flávio Lisbôa wrote:

> > ## Also, if someone knows a good way to synchro Scrolling and Music with
> 
> return [a.max, v] if v \> a.max

Well must be [RMXP.org](http://RMXP.org)… isn’t it?  
(although it’s been a while i’ve been there)  
I use the same username everywhere i go on the net… xD

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 30, 2007, 4:19am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/10 "2007-10-30T04:19:36Z")

</div>

From: trebor777 [[mailto:removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)]

# a = myhash.keys.sort[value-0.05…value+0.05]

# then i just use

# myhash[a[x]]

can you test without hash?

~\> a  
=\> [1, 1.25, 1.9, 2, 3, 3.5]  
~\> val  
=\> 1.85  
~\> a[val-0.5…val+0.5]  
=\> [1.25, 1.9]  
~\> a.slice (val-0.5…val+0.5)  
=\> [1.25, 1.9]

kind regards -botp

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 30, 2007, 2:47am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/11 "2007-10-30T02:47:51Z")

</div>

On Oct 29, 2007, at 2:19 PM, trebor777 wrote:

> in a range
> 
> It’s for a little music game, where player has to tap at the right  
> moment,  
> notes are register in a array, with the correct time, and as  
> players can’t  
> be accurate as a computer, i need some error margin. I working  
> with 0.05  
> rounded values.

install rbtree - it has upper\_bound and lower\_bound methods that do  
just this - otherwise you can do something like this:

cfp:~ \> cat a.rb  
require ‘alib’

Array.send :include, alib.bsearch

list = %w( a b c c c d e f )  
index = list.bsearch\_first {|x| x \<=\> “c”}  
p list[index - 1 … index + 1]

list = %w( a b c c c d e f )  
index = list.bsearch\_last {|x| x \<=\> “c”}  
p list[index - 1 … index + 1]

cfp:~ \> ruby a.rb  
[“b”, “c”, “c”]  
[“c”, “c”, “d”]

a @ [http://codeforpeople.com/](http://codeforpeople.com/)

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 30, 2007, 6:03am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/12 "2007-10-30T06:03:02Z")

</div>

trebor777 wrote:

> as i’m working with arrays, containing numbers, but with no regular step…  
> it will change i think.  
> example…
> 
> a = [1, 1.25, 2, 3, 3.5]
> 
> if i give 1.85, it gives me 1.25 and 2

Of course there are many ways. Here’s one. Add your target value to  
the array and sort, then return the values before and after it in  
sequence.

Note that this code ‘wraps’ the values in the array – a target value  
lower than the lowest value in the array, or higher than the highest  
value, will return the starting and ending values.

#!/usr/bin/ruby -w

# a is array of values, x is target value

def nearest(a,x)  
tmp = a.sort  
tmp \<\< x  
tmp.sort!  
i = tmp.index x  
[tmp[i-1], tmp[i+1]]  
end

a = [1, 1.25, 2, 3, 3.5]  
x = ARGV.shift.to\_i

a,b = nearest(a,x)  
puts “%0.2f =\> %0.2f,%0.2f” % [x, a, b]

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 30, 2007, 4:21am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/13 "2007-10-30T04:21:21Z")

</div>

On Behalf Of 7stud --:

# a = [1.25, 1, 3, 1.9, 1.95, 2.1, 2.2, 1.5]

# target = 1.85

# closest\_lower = nil

# closest\_higher = nil

# a.each do |elmt|

# if elmt \< target

# if !closest\_lower or elmt \> closest\_lower

# closest\_lower = elmt

# end

# elsif elmt \> target

# if !closest\_higher or elmt \< closest\_higher

# closest\_higher = elmt

# end

# else #if elmt == target

# #do something

# end

# end

# 

# Surprisingly, this is slightly faster–even for very large arrays:

# target = 1.85

# less\_than = []

# greater\_than = []

# a.each do |elmt|

# if elmt \< target

# less\_than \<\< elmt

# 

# elsif elmt \> target

# greater\_than \<\< elmt

# end

# end

# puts less\_than.max

# puts greater\_than.min

cool and straightforward. works in unordered list.

have you tried #partition?

~\> a  
=\> [1.25, 1, 3, 1.9, 1.95, 2.1, 2.2, 1.5]  
~\> [(parts=a.partition{|i| i\<=1.85}).first.max,parts.last.min]  
=\> [1.5, 1.9]

in 1.9, there is already group\_by, so  
~\> [(parts=a.group\_by{|e| e\<=1.85}.values).last.max,parts.first.min]  
=\> [1.5, 1.9]

…but we may be working too hard if lists is ordered though. and for  
ordered lists, a binary search like what ara posted should be the  
fastest.

kind regards -botp

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 30, 2007, 6:37am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/14 "2007-10-30T06:37:12Z")

</div>

Peña, Botp wrote:

> have you tried #partition?
> 
> ~\> a  
> =\> [1.25, 1, 3, 1.9, 1.95, 2.1, 2.2, 1.5]  
> ~\> [(parts=a.partition{|i| i\<=1.85}).first.max,parts.last.min]  
> =\> [1.5, 1.9]

No, I haven’t. Thanks for pointing the partition method out to me.

I must have been testing my first method on a different, longer array  
because now it runs slightly faster than my second method, as well as  
the partition solution, which makes more sense to me. Here are the  
results I get:

test1 exec time(1,000,000 loops): 10.348911 total  
test2 exec time(1,000,000 loops): 13.916226 total  
test4 exec time(1,000,000 loops): 12.912649 total

where test4 is this code:

a = [1.25, 1, 3, 2, 3.5, 4.25, 0.65, 1.5, 7.7, 9.2]  
target = 1.85

arr = a.partition do |elmt|  
elmt \< target  
end

closest\_lower = arr[0].max  
closest\_higher = arr[1].min  
end

But they are all pretty much equivalent. inject() is so slow, I just  
hit ctrl-c after what seems like 5 minutes.

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 30, 2007, 6:46am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/15 "2007-10-30T06:46:14Z")

</div>

ignore that post.  
what was i thinking, … again? :))

kind regards -botp

# -----Original Message-----

# From: Peña, Botp [[mailto:removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)]

# Sent: Tuesday, October 30, 2007 11:19 AM

# To: ruby-talk ML

# Subject: Re: find the closest items in an array to a given value.

# 

# From: trebor777 [[mailto:removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)]

# # a = myhash.keys.sort[value-0.05…value+0.05]

# # then i just use

# # myhash[a[x]]

# 

# can you test without hash?

# 

# ~\> a

# =\> [1, 1.25, 1.9, 2, 3, 3.5]

# ~\> val

# =\> 1.85

# ~\> a[val-0.5…val+0.5]

# =\> [1.25, 1.9]

# ~\> a.slice (val-0.5…val+0.5)

# =\> [1.25, 1.9]

# 

# kind regards -botp

# 

#

---

<div class="post-metadata">

**Author:** ![trebor777](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/a9adbd/32.png) [@trebor777](https://www.ruby-forum.com/u/trebor777)\
**Post date:** [October 31, 2007, 8:55am UTC](https://www.ruby-forum.com/t/find-the-closest-items-in-an-array-to-a-given-value/118661/16 "2007-10-31T08:55:54Z")

</div>

2007/10/29, David A. Black [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> Hi –
> 
> On Tue, 30 Oct 2007, Robert K. wrote:
> 
> > PS: A nice task for #inject. 🙂
> 
> Is that your .sig? 🙂

Not until now. Thanks for the inspiration!

Cheers

robert