根据 K，二分查找数组中与目标最接近的数字。（C 语言）

Question

我正在学习C语言的二分搜索并正在努力解决这个问题。 给定一个上升数组（没有重复数字）、目标值和数字 K，我需要找到最接近目标值（在数组中）的值，但是根据 K. 例如： 对于数组 {1, 2, 3, 4, 5, 6} 和目标值 4。 如果 k=1，我们返回 4，因为它是最接近的值。 如果 k=2，我们返回 3（3,5 与目标=4 的距离相等，在这种情况下，我们返回较小数字的值） 如果 k=3 我们返回 5。 *目标值不必包含在数组中。 到目前为止，我编写了这段代码，它执行基本的二分搜索来查找目标值的大致位置。 但我正在努力让 for 循环根据 K 返回值，因为允许的计算复杂度是 log(n)+k，我很确定我需要利用 for 循环。 我希望得到一些关于如何从现在开始继续的指导。

#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){

}

Answer 1

1. 使用二分查找查找数组中最接近目标的数字（如果存在则等于目标）。

2. 设置上位置和下位置等于找到位置的索引。

3. 重复 k−1 次：检查刚刚超出下位置的数组元素和刚刚超出上位置的元素。确定哪一个更接近目标。如果相等，优先选择较低的位置。将选择的位置调整到远一点。

完成后，最近调整位置的元素就是要返回的值。