C++寻找数组中最接近目标的数字 |21xrx.com

C++寻找数组中最接近目标的数字

2023-07-05 02:44:02 深夜i -- --

C++ 数组最接近目标数字

在C++编程中，寻找数组中最接近目标的数字是一项常见的任务。这种情况可能出现在很多应用中，比如游戏、财务等领域。

遍历数组并逐个比较元素是最基本的方法。但是，这种方法的时间复杂度较高，当数组很大时，时间会花费很长。下面介绍一种更高效的方法。

1. 对数组进行排序

对数组进行排序可以使查找更加方便。C++标准库中提供了sort()函数可以对数组进行排序，如下所示：

sort(arr, arr + n);

其中，arr是待排序的数组，n是数组的长度。

2. 利用二分查找

我们可以采用二分查找的方法，在排序后的数组中查找最接近目标的数字。这种方法具有时间复杂度O(log2n)，效率比遍历数组高得多。

具体方法如下：

（1）找到目标值在数组中的位置，如果数组中不存在该目标值，就找到目标值的插入位置（在哪个位置插入目标值才能使数组有序）。

int index = lower_bound(arr, arr + n, target) - arr;

（2）在目标值的左边和右边分别查找最接近目标的数字。

int left = index - 1, right = index;

int result = 0;

while (left >= 0 || right < n)

{

if (left >= 0 && right < n)

{

if (abs(arr[left] - target) <= abs(arr[right] - target))

// 如果左边的距离更短

{

result = arr[left];

left--;

}

else

{

result = arr[right];

right++;

}

else if (left >= 0)

{

result = arr[left];

left--;

}

else

{

result = arr[right];

right++;

}

以上代码中，利用了C++标准库中的lower_bound()函数来查找目标值在数组中的位置。如果数组中不存在该目标值，则返回的是目标值的排序位置。

然后，在目标值的左边和右边分别查找最接近目标值的数字，找到哪一个离目标值更近，就更新result。如果左边和右边的距离相等，则选择左边的数字。当左边或者右边超过了数组的边界，就停止查找。

3. 完整代码

下面是完整的C++代码：

#include

using namespace std;

int main()

{

int arr[] = 4;

int n = sizeof(arr) / sizeof(int);

int target = 13;

sort(arr, arr + n);

int index = lower_bound(arr, arr + n, target) - arr;

int left = index - 1, right = index;

int result = 0;

while (left >= 0 || right < n)

{

if (left >= 0 && right < n)

{

if (abs(arr[left] - target) <= abs(arr[right] - target))

{

result = arr[left];

left--;

}

else

{

result = arr[right];

right++;

}

else if (left >= 0)

{

result = arr[left];

left--;

}

else

{

result = arr[right];

right++;

}

cout << "The number closest to the target is: " << result << endl;

return 0;

}

这段代码中，我们首先定义了一个数组arr和它的长度n，然后定义了目标值target。接着，使用sort()函数对数组进行排序，获取目标值在数组中的位置index，最后通过二分查找方法找到最接近目标值的数字并输出。

总结

以上是关于C++寻找数组中最接近目标的数字的方法。在实际开发中，针对不同场景的不同需求，我们需要灵活运用不同的算法。掌握这些方法，可以提高程序效率，提升程序的性能。

上一篇: idea打包java可执行jar包

下一篇: NodeJS设计模式第三版

评论区

()

相似文章