Trova il valore più grande più piccolo di x in una matrice ordinata

Question

Supponiamo di disporre di una matrice ordinata di numeri interi int[] e di cercare il valore più piccolo più vicino a un numero di input.

per esempio se la matrice contiene (1), (23), (57), (59), (120) e l'ingresso è 109, l'uscita dovrebbe essere 59.

sto solo cercando di vedere i suggerimenti e confrontare gli approcci che ho già.

Answer 1

Utilizzare Array.BinarySearch. Se l'input è presente nell'elenco, restituirà l'indice e, in caso contrario, restituirà il complemento dell'indice del primo valore più grande. Basta invertire il risultato e sottrarre uno per ottenere l'indice del valore più vicino più piccolo.

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

Si noti che se si dispone di un ingresso più piccolo del più piccolo elemento, non si ha una risposta ben definita.

Answer 2

utilizzando Linq:

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

Forse non il più veloce, ma probabilmente il più facile da implementare. Inoltre, non fa affidamento sull'array che viene ordinato, come fa la ricerca binaria.

Si noti che la chiamata a Max genererà un'eccezione se il filtro Where non produce alcun elemento, pertanto è consigliabile verificare se è possibile.

Answer 3

mi piacerebbe andare per una soluzione LINQ (aggiornato: per aggiungere un po 'di più il codice di smettere di essere simile a soluzione simile di paura):

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

solo per estrapolare sulle altre soluzioni LINQ questo metodo di estensione restituirà -1 se nessun oggetto si inserisce il filtro e si attende che la lista è tutti i numeri interi positivi

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

utilizzo sarebbe simile a questa:

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