Найти наибольшее значение меньше 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 не даст никаких элементов, поэтому вы можете захотетьпроверьте, если это возможно.

Answer 3

Я бы выбрал решение 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...

Answer 4

int getIndex( long[] list, long value )
{
    int top = 0;
    int bot = list.length-1;
    int mid=0;
    while ( top <= bot )
    {
        mid = (top+bot)/2; // NB integer arithmetic
        if ( value < list[mid] )
        {
            if ( mid == 0 )
                // value < than first item
                return -1;  
            else
                bot = mid-1;
        }
        else    // value >= list[mid]
        {
            if ( mid == list.length-1 )
                // value is >= last item
                break;
            else if ( value >= list[mid+1] )
                top = mid+1;
            else // list[mid] must be biggest <= value
                break;
        }
    }
    return mid;
}

Answer 5

просто для экстраполяции на другие решения 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);