在排序数组中查找最接近n的值而不进行遍历 [英] Finding the closest value to n, without going over, in a sorted array

问题描述

对于这个问题，我有一个双精度数组.我需要能够快速有效地找到最接近但不超过n的值的索引.效率是关键，分配状态可以在O(log n)中完成，因此我认为可以通过某种修改后的二进制搜索来完成.

For this problem I have a sorted Array of doubles. I need to be able to quickly and efficiently find index of the value that is closest to, but not over, n. Efficiency is key, the assignment states is can be done in O(log n) so I assume it can be done with some sort of modified binary search.

我知道这已经被问过了，但是我发现的所有答案都假设是未排序的数组，或者只是遍历整个数组比较差异.

I know this has been asked before but all answers I found either assumed an unsorted array or simply looped through the entire array comparing differences.

任何指导表示赞赏.谢谢.

Any guidance is appreciated. Thank you.

推荐答案

是的，您可以通过修改后的二进制搜索来完成；只需照常查找数字即可；

Yes, you can do it with a modified binary search; just look for the number as usual and;

• 如果找到它，它是正确的数字(接近，但不超过)
• 如果找不到，则检查的最后一个数字是您的数字(您已经看过上面的数字一次，发现它太高了)
• 如果您找到它，并且最后检查的号码结束了，我想您将找到如何找到下一个最高的数字.

请记住，也要考虑一些错误条件，您会很好的:)

Just remember that there are some error conditions to consider too and you'll do fine :)

这篇关于在排序数组中查找最接近n的值而不进行遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！