---
# System prepended metadata

title: 0658. Find K Closest Elements
tags: [Leetcode, BFS, FaceBook, Sliding Window, Binary Search, Medium]

---

# 0658. Find K Closest Elements
###### tags: `Leetcode` `Medium` `FaceBook` `Binary Search` `BFS` `Sliding Window`
Link: https://leetcode.com/problems/find-k-closest-elements/
## 思路
非常巧妙的一道题
**看到sorted array就要想到binary search**
对左边界进行binary search，移动的条件是 如果arr[mid+k]-x>x-arr[mid]的时候，移动右指针，因为这说明arr[mid]+k以及后面的数不可能出现在结果当中，如果出现的话距离更小的arr[mid]就不能出现在答案里面了，反之同理

这里要注意的是**移动条件**，如果写```Math.abs(arr[mid+k]-x)>Math.abs(x-arr[mid])``` 那么如果遇到两个值相等的情况则容易出错
例如[1,2,2,2,2,2,2,3,3] x = 3,k = 3,答案就会变成[2,2,2]
（如果不理解的话，可以看这个网站(https://leetcode.com/problems/find-k-closest-elements/discuss/106426/JavaC%2B%2BPython-Binary-Search-O(log(N-K)-%2B-K)）
## Code
```java=
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> ans = new ArrayList<>();
        int start = 0;
        int end = arr.length-k;
        while(start<end){
            int mid = (start+end)/2;
            if(x-arr[mid]>arr[mid+k]-x){
                start = mid+1;
            }
            else{
                end = mid;
            }
        }
        for(int i = start;i < start+k;i++){
            ans.add(arr[i]);
        }
        return ans;
    }
}
```