Find K Closest Elements

Given a sorted integer array arr, two integers x and k, find the k closest elements to x in the array. The result should be sorted in ascending order by the absolute difference between each element and x. If there is a tie, the smaller elements are preferred.

Example:

Input:

arr = [1, 2, 3, 4, 5]
x = 3
k = 3

Output:

[2, 3, 4]

Explanation: In the input array, the absolute differences between each element and x are [2, 1, 0, 1, 2]. The closest k=3 elements to x=3 are [2, 3, 4].

Solution in C++:

#include <iostream>
#include <vector>
#include <algorithm>

// Function to find k closest elements to x in the sorted array
std::vector<int> findClosestElements(std::vector<int>& arr, int k, int x) {
    int left = 0;
    int right = arr.size() - k;

    // Use binary search to find the leftmost index of the k closest elements
    while (left < right) {
        int mid = left + (right - left) / 2;

        // If the absolute difference between x and arr[mid] is greater or equal to
        // the absolute difference between x and arr[mid+k], move the left pointer to mid+1
        if (std::abs(x - arr[mid]) >= std::abs(x - arr[mid + k])) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    // Return the k closest elements using the leftmost index found by binary search
    return std::vector<int>(arr.begin() + left, arr.begin() + left + k);
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5};
    int x = 3;
    int k = 3;

    std::vector<int> result = findClosestElements(arr, k, x);

    std::cout << "The " << k << " closest elements to " << x << " are: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

1. The findClosestElements function takes a reference to a sorted vector of integers arr, an integer k, and an integer x.
2. We use a binary search approach to find the leftmost index of the k closest elements. To do this, we initialize the left pointer to 0 and the right pointer to arr.size() - k, representing the valid range of starting indices for the k closest elements.
3. In each iteration of the binary search, we calculate the midpoint mid between left and right, and compare the absolute difference between x and arr[mid] with the absolute difference between x and arr[mid + k]. If the former is greater or equal, it means that the mid element is farther away from x compared to the element at mid + k. In this case, we move the left pointer to mid + 1. Otherwise, we update the right pointer to mid, as the leftmost index of the k closest elements must be before or equal to mid.
4. After the binary search, the left pointer points to the leftmost index of the k closest elements. We create a new vector using the left pointer and copy the k closest elements from the original array arr to the new vector.

Time Complexity:

The time complexity of this solution is O(log(n-k) + k), where n is the number of elements in the input array arr. The binary search takes O(log(n-k)) time, and copying the k closest elements to the new vector takes O(k) time.

Space Complexity:

The space complexity of this solution is O(k), where k is the number of elements to be returned in the output vector. This is because we create a new vector to store the k closest elements.