# Find value closest to input in list

Hi hail team,

If I have a number and a list of numbers, is there a fast way to find the closest value in the list to the input number? For example, if I have the number `5` and the list `[1, 7, 10, 15]`, I’d like to be able to quickly pull `7` from the list.

python’s `min` can do this, but I can’t seem to implement the same functionality with `hl.min()`. Is there a workaround, or am I missing something?

Thanks!

Hey @ch-kr !

You’re looking for `binary_search`:

``````ls = hl.array([1, 7, 10, 15])
x = hl.binary_search(ls, 7)
result = hl.or_missing(x != -1, ls[x])
result.show()
``````

I wasn’t aware you could finagle `min` to do this, how do you invoke it?

1 Like

ah neat, do you do this?

``````min([1, 7, 10, 15], key=lambda x: abs(x - 3))
``````

I should note, my solution only works for sorted lists.

This is the best I’ve got in Hail:

``````In [6]: def find_nearest(ls, x):
...:     def return_closest(l, r):
...:         return hl.if_else(hl.abs(l - x) < hl.abs(r - x), l, r)
...:     return hl.fold(return_closest, ls[0], ls[1:])

In [7]: find_nearest(ls, 5)
Out[7]: <Int32Expression of type int32>

In [8]: find_nearest(ls, 5).show()
+--------+
| <expr> |
+--------+
|  int32 |
+--------+
|      7 |
+--------+

In [9]: find_nearest(ls, 8).show()
+--------+
| <expr> |
+--------+
|  int32 |
+--------+
|      7 |
+--------+

In [10]: find_nearest(ls, 3).show()
+--------+
| <expr> |
+--------+
|  int32 |
+--------+
|      1 |
+--------+

In [11]: find_nearest(ls, 4).show()
+--------+
| <expr> |
+--------+
|  int32 |
+--------+
|      7 |
+--------+

``````
1 Like

`hl.binary_search` would return the index of the closest larger number in a sorted list. In the example, it works for input 5 (returns 7). But it doesn’t work for input 2 (also returns 7).

Another option would be to sort the list using a key and take the first element.

``````hl.sorted(ls, lambda n: hl.abs(n - input))[0]
``````

@danking’s `find_nearest` function would be more efficient than sorting though.

1 Like

I think binary search followed by checking the idx and idx - 1 would work, maybe?

1 Like

thank you all!!