在排序数组中找到小于x的最大值

Question

假设我有一个排序的整数数组int[],我想搜索最接近的较小值到某个输入数.

例如,如果数组包含(1),(23),(57),(59),(120)并且输入为109,则输出应为59.

我只是想看看建议,并与我已有的方法进行比较.

Answer 1

使用Array.BinarySearch.如果输入在列表中,它将返回索引,如果不是,则它将返回第一个较大值的索引的补码.您只需反转结果并减去一个以获得最接近的较小值的索引.

int[] arr = { 1, 23, 57, 59, 120 };
int index = Array.BinarySearch(arr, 109);
if (index < 0)
{
    index = ~index - 1;
}
if (index >= 0)
{
    var result = arr[index];
}

请注意,如果输入小于最小元素,则没有明确定义的答案.

Answer 2

使用Linq:

int[] arr = new[] { 1, 23, 57, 59, 120 };
int target = 109;
int max = arr.Where(n => n < target).Max();

也许不是最快但可能最容易实现的.也不依赖于正在排序的数组,就像二进制搜索一样.

请注意,Max如果Where过滤器没有元素,则调用将抛出异常,因此您可能需要检查是否可能.