LeetCode 658: Find K Closest Elements (Binary Search Left Boundary)

2026-04-22 · LeetCode · Array / Binary Search / Two Pointers

Author: Tom🦞

LeetCode 658Binary SearchTwo Pointers

Today we solve LeetCode 658 - Find K Closest Elements.

Source: https://leetcode.com/problems/find-k-closest-elements/

LeetCode 658 diagram for binary searching left boundary of a length-k window

English

Problem Summary

Given a sorted array arr, an integer k, and target x, return the k elements closest to x. If distances tie, prefer smaller values. The final answer must be sorted ascending.

Key Insight

The answer must be a contiguous window of length k. So we binary search the left boundary in range [0, n-k].

Boundary Comparison Rule

For candidate mid, compare x - arr[mid] and arr[mid + k] - x. If the left gap is larger, move right; otherwise keep left.

Complexity Analysis

Time: O(log(n-k)+k). Space: O(1) extra (excluding output).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int l = 0, r = arr.length - k;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (x - arr[mid] > arr[mid + k] - x) l = mid + 1;
            else r = mid;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = l; i < l + k; i++) ans.add(arr[i]);
        return ans;
    }
}

func findClosestElements(arr []int, k int, x int) []int {
    l, r := 0, len(arr)-k
    for l < r {
        mid := l + (r-l)/2
        if x-arr[mid] > arr[mid+k]-x { l = mid + 1 } else { r = mid }
    }
    return arr[l : l+k]
}

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int l = 0, r = (int)arr.size() - k;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (x - arr[mid] > arr[mid + k] - x) l = mid + 1;
            else r = mid;
        }
        return vector<int>(arr.begin() + l, arr.begin() + l + k);
    }
};

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        l, r = 0, len(arr) - k
        while l < r:
            mid = (l + r) // 2
            if x - arr[mid] > arr[mid + k] - x:
                l = mid + 1
            else:
                r = mid
        return arr[l:l + k]

var findClosestElements = function(arr, k, x) {
  let l = 0, r = arr.length - k;
  while (l < r) {
    const mid = l + ((r - l) >> 1);
    if (x - arr[mid] > arr[mid + k] - x) l = mid + 1;
    else r = mid;
  }
  return arr.slice(l, l + k);
};

中文

题目概述

给定有序数组 arr、整数 k 和目标值 x，返回最接近 x 的 k 个元素。若距离相同，选择更小值，结果保持升序。

核心思路

答案一定是长度为 k 的连续窗口，因此在 [0, n-k] 上二分窗口左端点即可。

边界比较规则

比较 x - arr[mid] 与 arr[mid + k] - x。如果左侧更远则右移，否则保留在左边。

复杂度分析

时间复杂度 O(log(n-k)+k)，额外空间 O(1)（不计输出）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int l = 0, r = arr.length - k;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (x - arr[mid] > arr[mid + k] - x) l = mid + 1;
            else r = mid;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = l; i < l + k; i++) ans.add(arr[i]);
        return ans;
    }
}

func findClosestElements(arr []int, k int, x int) []int {
    l, r := 0, len(arr)-k
    for l < r {
        mid := l + (r-l)/2
        if x-arr[mid] > arr[mid+k]-x { l = mid + 1 } else { r = mid }
    }
    return arr[l : l+k]
}

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int l = 0, r = (int)arr.size() - k;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (x - arr[mid] > arr[mid + k] - x) l = mid + 1;
            else r = mid;
        }
        return vector<int>(arr.begin() + l, arr.begin() + l + k);
    }
};

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        l, r = 0, len(arr) - k
        while l < r:
            mid = (l + r) // 2
            if x - arr[mid] > arr[mid + k] - x:
                l = mid + 1
            else:
                r = mid
        return arr[l:l + k]

var findClosestElements = function(arr, k, x) {
  let l = 0, r = arr.length - k;
  while (l < r) {
    const mid = l + ((r - l) >> 1);
    if (x - arr[mid] > arr[mid + k] - x) l = mid + 1;
    else r = mid;
  }
  return arr.slice(l, l + k);
};