Rechercher une valeur correspondante ou la plus proche dans un tableau

Comment rechercher et trouver, pour une valeur cible donnée, la valeur la plus proche dans un tableau?

Disons que j’ai ce tableau exemplaire:

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

Par exemple, lorsque je recherche avec la valeur cible 0, la fonction doit retourner 0; quand je recherche avec 3, il doit retourner 5; quand je recherche avec 14, il doit retourner 12.

Entrez le numéro que vous recherchez comme premier paramètre et le tableau des nombres sur le second:

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

Une approche paresseuse particulière consiste à faire en sorte que PHP sortinge le tableau en fonction de la distance par rapport au numéro recherché:

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

C’est la fonction haute performance que j’ai écrite pour les grands tableaux sortingés

Testé, la boucle principale n’a besoin que d’environ 20 itérations pour un tableau de 20000 éléments.

S’il vous plaît, le tableau doit être sortingé (croissant)!

 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 trouve l'élément le plus proche
  • ARRAY_NEAREST_LOWER trouve l'élément le plus proche qui est INFÉRIEUR
  • ARRAY_NEAREST_HIGHER trouve l'élément le plus proche qui est HIGHER

Usage:

 $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); 
  

Vous pouvez simplement utiliser array_search pour cela, il retourne une seule clé, s’il y a beaucoup d’instances de votre recherche trouvées dans le tableau, cela renverra le premier qu’il trouve.

Citation de PHP :

Si aiguille se trouve dans la botte de foin plus d’une fois, la première clé correspondante est renvoyée. Pour renvoyer les clés pour toutes les valeurs correspondantes, utilisez plutôt array_keys () avec le paramètre optionnel search_value.

Exemple d’utilisation:

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

Mettre à jour:

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

La mise en œuvre de Tim va le couper la plupart du temps. Néanmoins, pour les performances prudentes, vous pouvez sortinger la liste avant l’itération et casser la recherche lorsque la différence suivante est supérieure à la dernière.

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

Pour rechercher la valeur la plus proche dans un tableau d’objects, vous pouvez utiliser ce code adapté de la réponse de 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; } 

Cela devrait vous procurer ce dont vous avez besoin.

Considérant que le tableau d’entrée est sortingé par ordre asort() par exemple, vous serez beaucoup plus rapide pour effectuer une recherche dichotomique .

Voici une adaptation rapide et sale d’un code que j’utilise pour insérer un nouvel événement dans une liste d’événements Iterable sortingés par objects DateTime…

Ainsi, ce code renverra le point le plus proche à gauche (avant / plus petit).

Si vous souhaitez trouver le point mathématiquement le plus proche, envisagez de comparer la distance entre la valeur recherchée et la valeur renvoyée et le point situé immédiatement à droite (suivant) de la valeur renvoyée (si elle existe).

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

essayez ceci: (il n’a pas été testé)

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