# O(log n) Java, 1 line O(log(n) + k) Ruby

• 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.

• This post is deleted!

• @StefanPochmann Brilliant & Elegant way!
I trans it into c++ way:

``````vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0;
int right = arr.size()-k;
while(left<right){
int mid = left+(right-left)/2;
if(x-arr[mid]>arr[mid+k]-x){
left = mid+1;
}else{
right = mid;
}
}
auto S = arr.begin()+left;
auto E = arr.begin()+left+k;

return vector<int>(S,E);
}``````

• The java binary search solution is very impressive.

• @StefanPochmann Truely bravo,

• Fantastic solution! For those who might be confused on why/how that binary search solution works, here is a link that might be helpful (one of the best treatments on binary search I have seen so far). It was helpful to me. https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/

• This solution is really nice.

• Sorry, it's really hard to understand why the first i satisfying arr[i] is better than arr[i+k] is the i we want. Can you explain in detail why this termination condition works? Thank you.

• @jiaqi13

`arr[i]` and `arr[i+k]` are the only difference between the window `arr[i:i+k]` and the window `arr[(i+1):(i+1)+k]` one position further right. So that's actually testing which of those two windows is better.

"arr[i] is better than arr[i+k]" makes sure the window is right enough, and "first i" makes sure the window is left enough.

• I've read the link @LD_prettygood provided. but I still don't understand why this binary search works?

@StefanPochmann I believe many of us have the same question. Could you please explain it?

• @LeoShi I think the main idea here is try our best to make x in the center of the window [i, i + k]. Intuitively, that also corresponds to the definition of closest in the problem.

• @StefanPochmann Hey Stefan, fantastic!
I am still confused about the explanation on choosing which "window is better".
For the 2 windows : `arr[i:i+k]` and `arr[(i+1):(i+1)+k]`, let we define
`d1 = max(abs(target - arr[i]), abs(target - arr[i+k-1]))`
`d2 = max(abs(target - arr[i+1]), abs(target - arr[i+k]))`

I think the way to choose a "better window" is to choose the minimum (d1, d2), i.e the window with maximum distance towards target should be minimum. But this is wrong.

Could you explain more about your solution on how to decide "which window is better"?
Thanks!

I always learn a lot from you :)

• @StefanPochmann
Hi Stefan whether it's necessary to use

``````if(Math.abs(x - arr[mid]) > Math.abs(arr[mid + k] - x))
``````

``````if(x - arr[mid] > arr[mid + k] - x)
``````

in your Java Solution. And if not, why. Thanks.

• @wxl163530

It is not necessary.

Because if x < arr[mid], it means that the starting element of the result array must be within [lo, mid] (assume it starts from mid + 1, then arr[mid + 1] is closer to x than arr[mid], which is not possible because x < arr[mid] < arr[mid+1] );

if x > arr[mid + k], it means that the starting element of the result array must be within [mid + 1, hi]. (assume it starts from mid, then elements [mid, mid + k] are in the result array since arr[mid + k] is closer to x than arr[mid]. This means that there are k+1 elements in the result array, contradicting with the fact that there should be k elements in the result array.)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.