Найти наибольшее значение меньше x в отсортированном массиве
Предположим, у меня есть отсортированный массив целых чисел int [] , и я хочу выполнить поиск ближайшего меньшего значения к некоторому входному номеру.
Например, если массив содержит (1), (23), (57), (59), (120) и входное значение равно 109 Выход должен быть 59.
Я просто пытаюсь увидеть предложения и сравнить с подходами, которые у меня уже есть.
4 ответа
Используйте 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];
}
Обратите внимание, что если входные данные меньше наименьшего элемента, то у вас нет четко определенного ответа.
с использованием Linq:
int[] arr = new[] { 1, 23, 57, 59, 120 };
int target = 109;
int max = arr.Where(n => n < target).Max();
Возможно, не самый быстрый, но, вероятно, самый простой в реализации. Также не полагается на сортируемый массив, как это делает двоичный поиск.
Обратите внимание, что вызов Max вызовет исключение, если фильтр Where не даст никаких элементов, поэтому вы можете проверить это, если это возможно.
Я бы выбрал решение linq ( обновлено : чтобы добавить еще немного кода, чтобы он не был похож на аналогичное решение от страхов):
int[] arr1 = { 1, 23, 57, 59, 120 };
int maxResult;
string errorMsg;
try
{
maxResult = arr1.Where(x => x <= 109).Max();
}
catch(Exception e)
{
errorMsg = e.Message;
// do some error stuff here :)
return null;
}
// party on your maxResult...
просто для экстраполяции на другие решения LINQ этот метод расширения вернет -1, если ни один объект не соответствует фильтру, и ожидает, что список состоит из всех положительных целых чисел.
public static int SearchForLimit(this IEnuemerable<int> sequence, Predicate<int> filter)
{
return (from i in sequence
let n = filter(i) ? i : -1
select n).Max()
}
использование будет выглядеть следующим образом:
int[] arr1 = { 1, 23, 57, 59, 120 };
int limitedBy109 = arr1.SearchForLimit(i => i < 109);