基于K值查找数组中与目标值最接近的第K个元素（C语言）

给定升序无重复数组、目标值和数字K，需找出数组中与目标值最接近的第K个元素，规则如下：

• 若两个元素与目标值距离相同，取较小的元素
• 目标值不一定存在于数组中

示例：数组{1,2,3,4,5,6}、目标值4时，k=1返回4，k=2返回3，k=3返回5。

已完成基础二分查找定位目标值大致位置，但不知道如何实现符合O(log(n)+k)时间复杂度的取第K个元素的逻辑，当前代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/*******************************Defines****************************************/
#define ARR_MAX_LENGTH 50


/***************************Function declarations******************************/
/**
 * @fn k_closest_to_target
 * @brief Return the value of the k closest number to target in 'arr'.
 * @param arr - Sorted array of uniq integers.
 * @param n - Length of arr.
 * @param target - Integer number.
 * @param k - A non-negative number.
 * @return - value of kth closest to target.
 * @note If 2 different numbers are at the same distance from target we'll
 * treat the smaller one to be closer to target.
 * @note We assume k <= n.
 * @note Time complex is O(log(n) + k).
 */
int k_closest_to_target(int arr[], int n, int target, int k);
/*************************Put functions declarations here**********************/


/******************************************************************************/


int main() {
    int arr[ARR_MAX_LENGTH] = { 0 };
    int n =                     0;
    int target =                0;
    int k =                     0;

    printf("Please enter array length:\n");
    scanf("%d",&n);
    printf("Please enter target number:\n");
    scanf("%d",&target);
    printf("Please enter k:\n");
    scanf("%d",&k);
    printf("Please enter sorted and uniq array:\n");
    for (int i = 0; i < n; ++i) {
        scanf("%d",&arr[i]);
    }
    printf("%d\n",k_closest_to_target(arr,n,target,k));
    return 0;
}

/*************************Functions implementations****************************/
int k_closest_to_target(int arr[], int n, int target, int k){
    int high = n-1, low = 0;
    while (low <= high){
        int m = low + (high-low)/2;
        if (arr[m] == target)
            position_of_k_relative_to_target();
        if (arr[m] < target)
            low = m+1;
        else
            high = m-1;
    }
    return 0;
}
int distance(int arr[],int target){

}

核心思路 #

1. 二分定位边界：二分查找结束后，low指向第一个大于目标值的元素，high指向最后一个小于等于目标值的元素，以此锁定目标值附近的两个候选指针。
2. 双指针遍历选K个：从high和low开始，每次比较两指针指向元素与目标值的距离，按规则选择元素并移动对应指针，直到选出第K个元素：
   • 距离计算用abs(arr[ptr] - target)
   • 距离相同时，优先选择较小的元素（即左侧指针指向的元素）

修改后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

/*******************************Defines****************************************/
#define ARR_MAX_LENGTH 50

/***************************Function declarations******************************/
/**
 * @fn k_closest_to_target
 * @brief Return the value of the k closest number to target in 'arr'.
 * @param arr - Sorted array of uniq integers.
 * @param n - Length of arr.
 * @param target - Integer number.
 * @param k - A non-negative number.
 * @return - value of kth closest to target.
 * @note If 2 different numbers are at the same distance from target we'll
 * treat the smaller one to be closer to target.
 * @note We assume k <= n.
 * @note Time complex is O(log(n) + k).
 */
int k_closest_to_target(int arr[], int n, int target, int k);

/******************************************************************************/

int main() {
    int arr[ARR_MAX_LENGTH] = { 0 };
    int n =                     0;
    int target =                0;
    int k =                     0;

    printf("Please enter array length:\n");
    scanf("%d",&n);
    printf("Please enter target number:\n");
    scanf("%d",&target);
    printf("Please enter k:\n");
    scanf("%d",&k);
    printf("Please enter sorted and uniq array:\n");
    for (int i = 0; i < n; ++i) {
        scanf("%d",&arr[i]);
    }
    printf("%d\n",k_closest_to_target(arr,n,target,k));
    return 0;
}

/*************************Functions implementations****************************/
int k_closest_to_target(int arr[], int n, int target, int k){
    int low = 0, high = n - 1;
    // 二分查找确定目标值的插入位置边界
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            // 找到目标值，直接定位双指针到目标位置及左侧
            low = mid;
            high = mid - 1;
            break;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    // 未找到目标值时，high是最后一个小于target的索引，low是第一个大于target的索引
    int count = 0;
    int result = 0;
    // 双指针遍历选出第k个符合要求的元素
    while (count < k) {
        // 左侧指针越界，只能选右侧元素
        if (high < 0) {
            result = arr[low];
            low++;
        } 
        // 右侧指针越界，只能选左侧元素
        else if (low >= n) {
            result = arr[high];
            high--;
        } 
        else {
            int dist_high = abs(arr[high] - target);
            int dist_low = abs(arr[low] - target);
            // 按规则选择：距离小的优先；距离相同选较小元素
            if (dist_high < dist_low || (dist_high == dist_low && arr[high] < arr[low])) {
                result = arr[high];
                high--;
            } else {
                result = arr[low];
                low++;
            }
        }
        count++;
    }
    return result;
}

代码说明 #

1. 二分查找优化：找到目标值时直接调整指针位置，避免后续重复判断；未找到时，high和low自动落在插入位置的两侧，无需额外计算。
2. 双指针逻辑：每次循环选择一个符合要求的元素，时间复杂度为O(k)，结合二分查找的O(logn)，整体满足题目要求的时间复杂度。
3. 边界处理：覆盖了目标值小于所有元素、大于所有元素等极端情况，确保逻辑鲁棒性。

内容的提问来源于stack exchange，提问作者Razi Al Ashhab