¿Cómo puedo encontrar el elemento de matriz más cercano a un número arbitrario (no miembro)?

Question

Preguntas aparentemente similares: "Finding closest number in an array" (en Java) y "find nearest match to array of doubles" (en realidad es un problema de geografía).

Tengo una matriz (ordenada) de dobles. Dado un número arbitrario (que puede o no ser una coincidencia exacta para uno de los elementos de la matriz), ¿cómo puedo devolver el índice del número que es la coincidencia más cercana?

Por ejemplo, utilizando la siguiente matriz:

• 1,8
• 2,4
• 2,7
• 3,1
• 4,5

Consulta de 2,5 volvería con un índice de 1 , que corresponde al valor de 2.4.

Puntos de bonificación para detectar valores que se encuentran completamente fuera del rango de los elementos de la matriz. Por ejemplo, si usa la matriz listada anteriormente, su código puede decidir que 4.6 está dentro, pero 5.9 está fuera. Si quieres probar esta parte de la pregunta, los detalles están en tus manos.

Answer 1

Array.BinarySearch, que devuelve:

El índice del valor especificado en la matriz especificada, si se encuentra el valor. Si no se encuentra el valor y el valor es menor que uno o más elementos en el conjunto, un número negativo que es el complemento a nivel de bit del índice del primer elemento que es mayor que el valor. Si no se encuentra el valor y el valor es mayor que cualquiera de los elementos en el conjunto, un número negativo que es el complemento bit a bit de (el índice del último elemento más 1).

Ahora que no le conseguirá el 100% del camino, ya que se sabrá el número es ya sea menor o mayor que el partido, pero en realidad sólo te deja con dos índices para comprobar.

Answer 2

Algo como esto:

double[] values = new double[] 
{ 
    1.8, 
    2.4, 
    2.7, 
    3.1, 
    4.5 
}; 

double difference = double.PositiveInfinity; 
int index = -1; 

double input = 2.5; 

for (int i = 0; i < values.Length; i++) 
{ 
    double currentDifference = Math.Abs(values[i] - input); 

    if (currentDifference < difference) 
    { 
     difference = currentDifference; 
     index = i; 
    } 

    // Stop searching when we've encountered a value larger 
    // than the inpt because the values array is sorted. 
    if (values[i] > input) 
     break; 
} 

Console.WriteLine("Found index: {0} value {1}", index, values[index]); 

Answer 3

Una forma de hacer esto utilizando LINQ es así:

public int GetClosestIndex(List<double> doublelist, double targetvalue) 
{ 
    return doublelist.IndexOf(doublelist.OrderBy(d => Math.Abs(d - targetvalue)).ElementAt(0)); 
} 

Podría tener algunos problemas de rendimiento, pero si la lista no es tan largo, no debería ser un problema Además, si dos elementos están igualmente distantes del valor objetivo, devolverá el primer índice de esos.

Answer 4

Tal vez no sea la solución más rápida, pero sin duda agradable ojos dulces:

double search; 
double[] array; 

var nearest = (
    from value in array 
    orderby Math.Abs(value - search) 
    select value).First(); 

var index = array.IndexOf(nearest); 

Tenga en cuenta que esto será absolutamente ser más lento que un algoritmo de búsqueda binaria, ya que necesitan para procesar cada elemento de la matriz y medios de clasificación construyendo una tabla hash de esos artículos.

Answer 5

List<int> results; 
int target = 0; 
int nearestValue = 0; 
if (results.Any(ab => ab == target)) { 
    nearestValue= results.FirstOrDefault<int>(i => i == target); 
} else { 
    int greaterThanTarget = 0; 
    int lessThanTarget = 0; 
    if (results.Any(ab => ab > target) { 
     greaterThanTarget = results.Where<int>(i => i > target).Min(); 
    } 

    if (results.Any(ab => ab < target)) { 
     lessThanTarget = results.Where<int>(i => i < target).Max(); 
    } 

    if (lessThanTarget == 0) { 
     nearestValue= greaterThanTarget; 
    } else if (greaterThanTarget == 0) { 
     nearestValue = lessThanTarget; 
    } else { 
     if (target - lessThanTarget < greaterThanTarget - target) { 
      nearestValue = lessThanTarget; 
     } else { 
      nearestValue = greaterThanTarget; 
     } 
    } 
}