找到最接近数号的列表 [英] Find the closest number in a list of numbers

问题描述

我有常数列表。我需要找到在号码列表最接近数为x。关于如何实现这个算法任何想法？

I have a list of constant numbers. I need to find the closest number to x in the list of the numbers. Any ideas on how to implement this algorithm?

推荐答案

好了，你不能做到这一点的速度比 O（N），因为你必须检查所有号码确保你有最近的一个。这就是说，对发现的最小为什么不能用一个简单的变化，寻找一个与具有最小绝对差的 X 的？

Well, you cannot do this faster than O(N) because you have to check all numbers to be sure you have the closest one. That said, why not use a simple variation on finding the minimum, looking for the one with the minimum absolute difference with x?

如果可以说该列表从开始有序（和它允许随机存取，如阵列），那么一个较好的方法是使用二进制搜索。当您结束搜索索引的我的（没有发现的 X 的），只挑选最好的出该元素及其邻国。

If you can say the list is ordered from the beginning (and it allows random-access, like an array), then a better approach is to use a binary search. When you end the search at index i (without finding x), just pick the best out of that element and its neighbors.

这篇关于找到最接近数号的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！