Найти наибольшее значение меньше, чем x в отсортированном массиве

Предположим, что у меня есть отсортированный массив целых чисел int[], и я хочу выполнить поиск ближайшего меньшего значения для некоторого номера ввода.

например, если массив содержит (1), (23), (57), (59), (120) и вход 109, выход должен быть 59.

Я просто пытаюсь увидеть предложения и сравнить с теми подходами, которые у меня уже есть.

Ответы

Ответ 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];
}

Обратите внимание, что если у вас есть вход меньше наименьшего элемента, у вас нет четко определенного ответа.

Ответ 2

с использованием Linq:

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

Возможно, не самый быстрый, но, возможно, самый простой в реализации. Также не полагается на сортируемый массив, как это делает бинарный поиск.

Обратите внимание, что вызов Max генерирует исключение, если фильтр Where не содержит элементов, поэтому вы можете проверить, возможно ли это.

Ответ 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...

Ответ 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;
}

Ответ 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);