Find K Closest Elements [Medium] — Binary Search + Two Ptr

Problem Statement

Given sorted array, integer k, and integer x, return the k closest integers to x. If tie, prefer smaller. Return sorted.

Input: arr=[1,2,3,4,5], k=4, x=3 → Output: [1,2,3,4]

Intuition

Binary search for left boundary: search in range [0, n-k]. At each mid, decide if window starts at mid or mid+1: if x - arr[mid] > arr[mid+k] - x, the right element is closer → move left boundary right.

Solutions

C++

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

Java

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

Python

def findClosestElements(arr: list[int], k: int, x: int) -> list[int]:
    lo, hi = 0, len(arr)-k
    while lo < hi:
        mid = (lo+hi)//2
        if x - arr[mid] > arr[mid+k] - x: lo = mid+1
        else: hi = mid
    return arr[lo:lo+k]

Complexity

Time: O(log(n-k) + k), Space: O(1)