Trova un valore corrispondente o il più vicino in un array

Come posso cercare e trovare, per un dato valore nominale, il valore più vicino in un array?

Diciamo che ho questo array esemplare:

array(0, 5, 10, 11, 12, 20) 

Ad esempio, quando eseguo una ricerca con il valore objective 0, la funzione deve restituire 0; quando cerco con 3, restituirà 5; quando cerco con 14, restituirà 12.

Passa il numero che stai cercando come primo parametro e l’array di numeri per il secondo:

 function getClosest($search, $arr) { $closest = null; foreach ($arr as $item) { if ($closest === null || abs($search - $closest) > abs($item - $search)) { $closest = $item; } } return $closest; } 

Un particolare approccio pigro consiste nel disporre in PHP l’array in base alla distanza dal numero cercato:

 $num = 3; $array = array(0, 5, 10, 11, 12, 20); foreach ($array as $i) { $smallest[$i] = abs($i - $num); } asort($smallest); print key($smallest); 

Questa è la funzione ad alte prestazioni che ho scritto per i grandi array ordinati

Testato, il ciclo principale richiede solo ~ 20 iterazioni per un array con 20000 elementi.

Per favore, la matrice deve essere ordinata (crescente)!

 define('ARRAY_NEAREST_DEFAULT', 0); define('ARRAY_NEAREST_LOWER', 1); define('ARRAY_NEAREST_HIGHER', 2); /** * Finds nearest value in numeric array. Can be used in loops. * Array needs to be non-assocative and sorted. * * @param array $array * @param int $value * @param int $method ARRAY_NEAREST_DEFAULT|ARRAY_NEAREST_LOWER|ARRAY_NEAREST_HIGHER * @return int */ function array_numeric_sorted_nearest($array, $value, $method = ARRAY_NEAREST_DEFAULT) { $count = count($array); if($count == 0) { return null; } $div_step = 2; $index = ceil($count / $div_step); $best_index = null; $best_score = null; $direction = null; $indexes_checked = Array(); while(true) { if(isset($indexes_checked[$index])) { break ; } $curr_key = $array[$index]; if($curr_key === null) { break ; } $indexes_checked[$index] = true; // perfect match, nothing else to do if($curr_key == $value) { return $curr_key; } $prev_key = $array[$index - 1]; $next_key = $array[$index + 1]; switch($method) { default: case ARRAY_NEAREST_DEFAULT: $curr_score = abs($curr_key - $value); $prev_score = $prev_key !== null ? abs($prev_key - $value) : null; $next_score = $next_key !== null ? abs($next_key - $value) : null; if($prev_score === null) { $direction = 1; }else if ($next_score === null) { break 2; }else{ $direction = $next_score < $prev_score ? 1 : -1; } break; case ARRAY_NEAREST_LOWER: $curr_score = $curr_key - $value; if($curr_score > 0) { $curr_score = null; }else{ $curr_score = abs($curr_score); } if($curr_score === null) { $direction = -1; }else{ $direction = 1; } break; case ARRAY_NEAREST_HIGHER: $curr_score = $curr_key - $value; if($curr_score < 0) { $curr_score = null; } if($curr_score === null) { $direction = 1; }else{ $direction = -1; } break; } if(($curr_score !== null) && ($curr_score < $best_score) || ($best_score === null)) { $best_index = $index; $best_score = $curr_score; } $div_step *= 2; $index += $direction * ceil($count / $div_step); } return $array[$best_index]; } 
  • ARRAY_NEAREST_DEFAULT trova l'elemento più vicino
  • ARRAY_NEAREST_LOWER trova l'elemento più vicino che è INFERIORE
  • ARRAY_NEAREST_HIGHER trova l'elemento più vicino che è SUPERIORE

Uso:

 $test = Array(5,2,8,3,9,12,20,...,52100,52460,62000); // sort an array and use array_numeric_sorted_nearest // for multiple searches. // for every iteration it start from half of chunk where // first chunk is whole array // function doesn't work with unosrted arrays, and it's much // faster than other solutions here for sorted arrays sort($test); $nearest = array_numeric_sorted_nearest($test, 8256); $nearest = array_numeric_sorted_nearest($test, 3433); $nearest = array_numeric_sorted_nearest($test, 1100); $nearest = array_numeric_sorted_nearest($test, 700); 
  

Puoi semplicemente usare array_search per questo, restituisce una singola chiave, se ci sono molte istanze della tua ricerca trovate all’interno dell’array, restituirà il primo che trova.

Citazione da PHP :

Se l’ago viene trovato nel pagliaio più di una volta, viene restituita la prima chiave corrispondente. Per restituire le chiavi per tutti i valori corrispondenti, utilizzare invece array_keys () con il parametro search_value facoltativo.

Esempio di utilizzo:

 if(false !== ($index = array_search(12,array(0, 5, 10, 11, 12, 20)))) { echo $index; //5 } 

Aggiornare:

 function findNearest($number,$Array) { //First check if we have an exact number if(false !== ($exact = array_search($number,$Array))) { return $Array[$exact]; } //Sort the array sort($Array); //make sure our search is greater then the smallest value if ($number < $Array[0] ) { return $Array[0]; } $closest = $Array[0]; //Set the closest to the lowest number to start foreach($Array as $value) { if(abs($number - $closest) > abs($value - $number)) { $closest = $value; } } return $closest; } 

L’implementazione di Tim la taglierà la maggior parte del tempo. Tuttavia, per le prestazioni caute, è ansible ordinare l’elenco prima dell’iterazione e interrompere la ricerca quando la differenza successiva è maggiore dell’ultima.

  $item) { if (abs($needle - $haystack[$closest_value_index]) > abs($item - $needle)) { $closest_value_index = $i; } if ($closest_value_index === $last_closest_value_index) { break; } } return $closest_value_index; } function getClosestValue ($needle, $haystack) { return $haystack[getIndexOfClosestValue($needle, $haystack)]; } // Test $needles = [0, 2, 3, 4, 5, 11, 19, 20]; $haystack = [0, 5, 10, 11, 12, 20]; $expectation = [0, 0, 1, 1, 1, 3, 5, 5]; foreach ($needles as $i => $needle) { var_dump( getIndexOfClosestValue($needle, $haystack) === $expectation[$i] ); } 

Per cercare il valore più vicino in una serie di oggetti è ansible utilizzare questo codice adattato dalla risposta di Tim Cooper .

  rand(100, 1000) ); // print array print_r($images); // adapted function from Tim Copper's solution // https://stackoverflow.com/a/5464961/496176 function closest($array, $member, $number) { $arr = array(); foreach ($array as $key => $value) $arr[$key] = $value->$member; $closest = null; foreach ($arr as $item) if ($closest === null || abs($number - $closest) > abs($item - $number)) $closest = $item; $key = array_search($closest, $arr); return $array[$key]; } // object needed $needed_object = closest($images, 'width', 320); // print result print_r($needed_object); ?> 
 function closestnumber($number, $candidates) { $last = null; foreach ($candidates as $cand) { if ($cand < $number) { $last = $cand; } else if ($cand == $number) { return $number; } else if ($cand > $number) { return $last; } } return $last; } 

Questo dovrebbe farti ciò di cui hai bisogno.

Considerando che l’array di input è ordinato in ordine ascendente asort() ad esempio, sarà molto più veloce cercare usando una ricerca dicotomica .

Ecco un rapido e sporco adattamento di un codice che sto usando per inserire un nuovo evento in un elenco di eventi Iterable ordinato per oggetti DateTime …

Quindi questo codice restituirà il punto più vicino a sinistra (prima / più piccolo).

Se desideri trovare il punto matematicamente più vicino: considera il confronto tra la distanza del valore di ricerca con il valore di ritorno e il punto immediatamente a destra (successivo) del valore di ritorno (se esiste).

 function dichotomicSearch($search, $haystack, $position=false) { // Set a cursor between two values if($position === false) { $position=(object) array( 'min' => 0, 'cur' => round(count($haystack)/2, 0, PHP_ROUND_HALF_ODD), 'max' => count($haystack) ); } // Return insertion point (to push using array_splice something at the right spot in a sorted array) if(is_numeric($position)){return $position;} // Return the index of the value when found if($search == $haystack[$position->cur]){return $position->cur;} // Searched value is smaller (go left) if($search <= $haystack[$position->cur]) { // Not found (closest value would be $position->min || $position->min+1) if($position->cur == $position->min){return $position->min;} // Resetting the interval from [min,max[ to [min,cur[ $position->max=$position->cur; // Resetting cursor to the new middle of the interval $position->cur=round($position->cur/2, 0, PHP_ROUND_HALF_DOWN); return dichotomicSearch($search, $haystack, $position); } // Search value is greater (go right) // Not found (closest value would be $position->max-1 || $position->max) if($position->cur < $position->min or $position->cur >= $position->max){return $position->max;} // Resetting the interval from [min,max[ to [cur,max[ $position->min = $position->cur; // Resetting cursor to the new middle of the interval $position->cur = $position->min + round(($position->max-$position->min)/2, 0, PHP_ROUND_HALF_UP); if($position->cur >= $position->max){return $position->max;} return dichotomicSearch($search, $haystack, $position); } 

prova questo: (non è stato testato)

 function searchArray($needle, $haystack){ $return = $haystack[0]; $prevReturn = $return; foreach($haystack as $key=>$val){ if($needle > $val) { $prevReturn = $return; $return = $val; } if($val >= $needle) { $prevReturn = $return; $return = $val; break; } } if((($return+$needle)/2) > (($prevReturn+$needle)/2)){ //means that the needle is closer to $prevReturn return $prevReturn; } else return $return; }