K Closest Numbers (Find the K Elements Nearest a Target in a Sorted Array)

• K Closest Numbers is a Top K Elements problem that exploits the sorted order of the input array.
• Binary search finds the position of the target or its insertion point in O(log N) time.
• Two pointers straddle the target and expand outward, picking whichever neighbour is closer.
• The K closest elements always form a contiguous window in a sorted array.
• A less-than-or-equal comparison on the left side implements the tie-break preferring the smaller number.
• Time is O(log N + K) and space is O(K) for the result.

What is the K Closest Numbers problem?

Given a sorted array of integers, a target value X, and a count K, find the K numbers in the array that are closest to X. If two numbers are equally close to X, prefer the smaller number. Return the result in sorted order.

For example, given [1, 3, 5, 7, 9], target = 6, K = 3, the closest numbers are [5, 7, 3] by distance, returned sorted as [3, 5, 7].

Why does binary search help here?

Because the array is sorted, binary search finds the exact position of the target or its insertion point in O(log N) time. This gives us the starting boundary for the two-pointer expansion. Without binary search, we would need to scan linearly to find where to start, wasting the sorted property.

package com.bank.service;

public class RateSearchService {

    /**
     * Finds the insertion point for the target rate in a sorted array.
     * Uses standard binary search.
     */
    static int findInsertionPoint(int[] rates, int target) {
        int low = 0, high = rates.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (rates[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low; // Insertion point
    }

    public static void main(String[] args) {
        int[] rates = {300, 450, 550, 675, 800, 925};
        int target = 600;
        System.out.println("Insertion point: " + findInsertionPoint(rates, target));
    }
}

Insertion point: 3

How does the two-pointer expansion work?

After binary search gives us the insertion point, we set left = insertionPoint - 1 and right = insertionPoint. These two pointers straddle the target. We then pick K numbers by comparing the distances from each pointer to the target and choosing the closer one.

package com.bank.service;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.ArrayList;

public class KClosestRatesService {

    /**
     * Finds the K interest rates closest to the target rate.
     * Used by the National Bank of India advisory tool.
     */
    public static List<Integer> findKClosest(int[] rates, int target, int k) {
        int index = findInsertionPoint(rates, target);
        int left = index - 1;
        int right = index;
        Deque<Integer> result = new ArrayDeque<>();

        while (result.size() < k) {
            if (left >= 0 && (right >= rates.length
                    || target - rates[left] <= rates[right] - target)) {
                result.addFirst(rates[left]);
                left--;
            } else {
                result.addLast(rates[right]);
                right++;
            }
        }
        return new ArrayList<>(result);
    }

    static int findInsertionPoint(int[] rates, int target) {
        int low = 0, high = rates.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (rates[mid] < target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] rates = {300, 450, 550, 675, 800, 925};
        int target = 600;
        int k = 3;
        System.out.println("K closest rates to " + target + ": "
            + findKClosest(rates, target, k));
    }
}

javac -d out com/bank/service/KClosestRatesService.java
java -cp out com.bank.service.KClosestRatesService

K closest rates to 600: [450, 550, 675]

How does the tie-break work?

The comparison target - rates[left] <= rates[right] - target uses less-than-or-equal on the left side. When two candidates are equally distant from the target, the left (smaller) number is preferred. This satisfies the problem requirement of preferring the smaller number on ties.

Why do the K closest form a contiguous window?

In a sorted array, if two numbers a and b are both among the K closest to X and a < b, then every number between a and b must also be among the K closest. This is because any number between a and b is at most as far from X as the farther of a and b. This contiguity property is what makes the two-pointer approach correct.

What are the edge cases?

Several edge cases require attention.

• Target smaller than all elements: left pointer starts out of bounds, all K elements come from the right.
• Target larger than all elements: right pointer starts out of bounds, all K elements come from the left.
• K equals array length: return the entire array.
• Duplicate values: handled naturally by the comparison.

package com.bank.core;

import java.util.List;

public class KClosestEdgeCases {
    public static void main(String[] args) {
        int[] rates = {300, 450, 550, 675, 800};

        // Target below all elements
        System.out.println(findKClosest(rates, 100, 2)); // [300, 450]

        // Target above all elements
        System.out.println(findKClosest(rates, 1000, 2)); // [675, 800]

        // K equals array length
        System.out.println(findKClosest(rates, 600, 5)); // all elements
    }

    static List<Integer> findKClosest(int[] arr, int target, int k) {
        int idx = 0, lo = 0, hi = arr.length;
        while (lo < hi) { int m = lo + (hi - lo) / 2; if (arr[m] < target) lo = m + 1; else hi = m; }
        idx = lo; int l = idx - 1, r = idx;
        java.util.Deque<Integer> res = new java.util.ArrayDeque<>();
        while (res.size() < k) {
            if (l >= 0 && (r >= arr.length || target - arr[l] <= arr[r] - target)) res.addFirst(arr[l--]);
            else res.addLast(arr[r++]);
        }
        return new java.util.ArrayList<>(res);
    }
}

[300, 450]
[675, 800]
[300, 450, 550, 675, 800]

What is the time and space complexity?

The binary search takes O(log N) time. The two-pointer expansion takes O(K) time. Total time is O(log N + K). Space is O(K) for the result list. This is optimal: you cannot do better than log N to find the starting point and K to collect the results.

How is this different from using a heap?

A max-heap approach would iterate through the array, maintaining a heap of size K ordered by distance. This gives O(N log K) time, which is worse than O(log N + K) when the array is sorted. The two-pointer approach exploits the sorted property that a heap ignores.

| Approach | Time | Space | Requires sorted input? |
|---|---|---|---|
| Two-pointer after binary search | O(log N + K) | O(K) | Yes |
| Max-heap of size K | O(N log K) | O(K) | No |
| Sort then two-pointer | O(N log N + K) | O(N) | No |

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• Deque for sorted output: adding left picks to the front and right picks to the back of a deque naturally produces sorted output without a final sort step.
• Alternative binary search for window: instead of expanding from the center, binary search directly for the left boundary of the K-window, giving O(log(N-K) + K) time.
• Streaming variant: if the array is not fully available, a heap-based approach is necessary because you cannot binary search a stream.