【二分查找】658. 找到 K 个最接近的元素

 1 class Solution {
 2 public:
 3     vector<int> findClosestElements(vector<int>& arr, int k, int x) 
 4     {
 5         int size = arr.size();
 6 
 7         int left = 0;
 8         int right = size - 1;
 9 
10         int removeNums = size - k;
11 
12         while (removeNums > 0) 
13         {
14             if (x - arr[left] <= arr[right] - x) 
15             {
16                 right--;
17             } 
18             else 
19             {
20                 left++;
21             }
22             removeNums--;
23         }
24 
25         vector<int> res;
26         for (int i = left; i < left + k; i++) 
27         {
28             res.push_back(arr[i]);
29         }
30         return res;
31     }
32 };

 1 class Solution {
 2 public:
 3     vector<int> findClosestElements(vector<int>& arr, int k, int x) 
 4     {
 5         int size = arr.size();
 6 
 7         int left = 0;
 8         int right = size - k;
 9 
10         while (left < right) 
11         {
12             int mid = left + (right - left) / 2;
13            
14             // 尝试从长度为 k + 1 的连续子区间删除一个元素
15             // 从而定位左区间端点的边界值
16             if (x - arr[mid] > arr[mid + k] - x) 
17             {
18                 left = mid + 1;
19             } 
20             else 
21             {
22                 right = mid;
23             }
24         }
25 
26         vector<int> res;
27         for (int i = left; i < left + k; i++) 
28         {
29             res.push_back(arr[i]);
30         }
31         return res;
32     }
33 };