C++程序在数组中查找最接近的数字

在编程中，我们经常需要在一个已经排好序的数组中查找一个离目标值最近的数字。这种情况下我们需要一个十分高效的算法来避免性能损失，最常用的算法是二分查找。

什么是二分查找？

二分查找，也叫折半查找，是一种在有序数组中查找目标值的算法。该算法的基本思想是将待查找区间的中间位置作为比较对象，如果目标值等于该位置的值，则查找到了目标值；如果目标值大于该位置的值，则在右半部分继续查找；否则在左半部分继续查找。以此类推，直到查找到目标值或者区间为空为止。

实现二分查找

下面通过一个 C++ 示例代码来演示如何实现二分查找。

int binarySearch(int arr[], int l, int r, int target) {
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    // 左闭右闭查找，如果找不到返回 -1
    return -1;
}

这段代码实现了一个针对有序数组的二分查找函数 binarySearch，该函数接受以下参数：有序数组的指针 arr，查找区间左端点 l，右端点 r 和目标值 target。函数返回目标值在数组中的下标，找不到则返回 -1。

找到最接近的数字

在二分查找的基础上，我们可以通过比较区间两端点与目标值的差值，找到目标值所在的位置及其左右两侧的数字，然后比较两侧数字与目标值的差值，返回差值较小的数字。

int nearestNumber(int arr[], int l, int r, int target) {
    if (target <= arr[l]) {
        return arr[l];
    } else if (target >= arr[r]) {
        return arr[r];
    }
    int mid = binarySearch(arr, l, r, target);
    if (mid == -1) {
        return -1;
    }
    int left = mid - 1, right = mid + 1;
    while (left >= l && right <= r) {
        if (target - arr[left] <= arr[right] - target) {
            return arr[left];
        } else {
            return arr[right];
        }
    }
    return target - arr[left] <= arr[right] - target ? arr[left] : arr[right];
}

这段代码实现了一个找到最接近数字的函数 nearestNumber，该函数接受以下参数：有序数组的指针 arr，查找区间左端点 l，右端点 r 和目标值 target。函数返回数组中与目标值最接近的数字。