I binary-search for where the resulting elements start in the array. It's the first index `i`

so that `arr[i]`

is better than `arr[i+k]`

(with "better" meaning closer to or equally close to `x`

). Then I just return the `k`

elements starting there.

```
def find_closest_elements(arr, k, x)
arr[(0..arr.size).bsearch { |i| x - arr[i] <= (arr[i+k] || 1/0.0) - x }, k]
end
```

I think that's simpler than binary-searching for `x`

and then expanding to the left and to the right like I've seen in other binary search solutions.

Here's a Java version without using the library's binary search:

```
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
int lo = 0, hi = arr.size() - k;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (x - arr.get(mid) > arr.get(mid+k) - x)
lo = mid + 1;
else
hi = mid;
}
return arr.subList(lo, lo + k);
}
```

The binary search costs O(log n) (actually also just O(log (n-k)) and the `subList`

call probably only takes O(1). As @sagimann pointed out, `subList`

returns a view, not a separate copy. So it should only take O(1). Can be seen for example in `ArrayList`

's subList and the `SubList`

constructor it calls. I also checked `LinkedList`

, it gets its `subList`

method inherited from `AbstractList`

, where it also takes only O(1). And `AbstractList`

is a basis for most lists.

**Edit:** I also implemented it in Go now, to make it O(log n). **Edit 2:** Ha, didn't have to do that, as the Java version apparently already was O(log n) (I didn't originally know Java returns a view, only added that now). **Edit 3:** Lol, I had mistakenly written "Python" in the title instead of "Ruby" but apparently nobody noticed (and it's at 1800 views). Fixed that now.