Encuentra el valor más grande más pequeño que x en una matriz ordenada

Question

Supongamos que tengo una matriz ordenada de enteros int[], y quiero buscar el valor más pequeño más cercano a un número de entrada.

por ejemplo, si la matriz contiene (1), (23), (57), (59), (120) y la entrada es 109, la salida debe ser 59.

estoy tratando de ver sugerencias y comparar con los enfoques que ya tengo.

Answer 1

Use Array.BinarySearch. Si la entrada está en la lista, devolverá el índice, y si no, devolverá el complemento del índice del primer valor mayor. Simplemente invierte el resultado y resta uno para obtener el índice del valor menor más cercano.

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]; 
} 

Tenga en cuenta que si usted tiene una entrada más pequeña que el elemento más pequeño, no tiene una respuesta bien definida.

Answer 2

usando LINQ:

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

Tal vez no el más rápido, pero probablemente el más fácil de implementar. Además, no depende de que la matriz esté ordenada, como lo hace la búsqueda binaria.

Tenga en cuenta que la llamada a Max arrojará una excepción si el filtro Where no da como resultado ningún elemento, por lo que es posible que desee verificarlo si es posible.

Answer 3

yo iría a una solución LINQ (actualizado: añadir un poco más de código para detener de ser similar a la solución similar de miedo):

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

sólo para extrapolar las otras soluciones LINQ este método de extensión devolverá -1 si no hay objetos se ajusta el filtro y espera que la lista es todos los números enteros positivos

uso

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() 
} 

sería el siguiente:

int[] arr1 = { 1, 23, 57, 59, 120 }; 
int limitedBy109 = arr1.SearchForLimit(i => i < 109); 

Answer 5

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; 
}