Suchen Sie nach einem übereinstimmenden oder nächstliegenden Wert in einem Array

Wie kann ich den nächsten Wert in einem Array für einen bestimmten Zielwert suchen und finden?

Nehmen wir an, ich habe dieses beispielhafte Array:

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

Zum Beispiel, wenn ich mit dem Zielwert 0 suche, soll die function 0 zurückgeben; Wenn ich mit 3 suche, soll es 5 zurückgeben; Wenn ich mit 14 suche, soll es 12 zurückgeben.

Übergeben Sie die Nummer, nach der Sie suchen, als ersten Parameter und das Zahlenfeld an die zweite:

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

Ein besonders fauler Ansatz ist, dass PHP das Array nach der Entfernung zur gesuchten Nummer sortiert:

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

Dies ist eine Hochleistungsfunktion, die ich für sortierte große Arrays geschrieben habe

Getestet benötigt die Hauptschleife nur ~ 20 Iterationen für ein Array mit 20000 Elementen.

Bitte beachten Sie, dass das Array sortiert werden muss (aufsteigend)!

 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 findet das nächste Element
  • ARRAY_NEAREST_LOWER findet das nächste Element, das LOWER ist
  • ARRAY_NEAREST_HIGHER findet das nächste Element, das ARRAY_NEAREST_HIGHER ist

Verwendung:

 $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); 
 < ?php $arr = array(0, 5, 10, 11, 12, 20); function getNearest($arr,$var){ usort($arr, function($a,$b) use ($var){ return abs($a - $var) - abs($b - $var); }); return array_shift($arr); } ?> 

Sie können einfach array_search dafür verwenden, es gibt einen einzelnen Schlüssel zurück, wenn es viele Instanzen Ihrer Suche innerhalb des Arrays gefunden hat, würde es die erste zurückgeben, die es findet.

Zitat aus PHP :

Wenn die Nadel im Heuhaufen mehr als einmal gefunden wird, wird der erste übereinstimmende Schlüssel zurückgegeben. Um die Schlüssel für alle übereinstimmenden Werte zurückzugeben, verwenden Sie stattdessen array_keys () mit dem optionalen Parameter search_value.

Beispiel Verwendung:

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

Aktualisieren:

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

Tims Implementierung wird die meiste Zeit sparen. Trotzdem können Sie die Liste vor der Iteration sortieren und die Suche unterbrechen, wenn die nächste Differenz größer als die letzte ist.

 < ?php function getIndexOfClosestValue ($needle, $haystack) { if (count($haystack) === 1) { return $haystack[0]; } sort($haystack); $closest_value_index = 0; $last_closest_value_index = null; foreach ($haystack as $i => $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] ); } 

Um den nächsten Wert in einem Array von Objekten zu suchen, können Sie diesen angepassten Code aus Tim Coopers Antwort verwenden .

 < ?php // create array of ten objects with random values $images = array(); for ($i = 0; $i < 10; $i++) $images[ $i ] = (object)array( 'width' => 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; } 

Dies sollte dir helfen, was du brauchst.

Wenn man bedenkt, dass das Eingabearray beispielsweise in aufsteigender Reihenfolge asort() , ist die Suche nach einer dichotomischen Suche asort() schneller.

Hier ist eine kurze und schmutzige Anpassung von Code, den ich verwende, um ein neues Ereignis in eine Iterable- Ereignisliste einzufügen , sortiert nach DateTime-Objekten …

Daher wird dieser Code den nächsten Punkt links (vor / kleiner) zurückgeben.

Wenn Sie den mathematisch nächsten Punkt finden möchten: Vergleichen Sie den Abstand des Suchwerts mit dem Rückgabewert und den Punkt unmittelbar rechts (neben) des Rückgabewerts (falls vorhanden).

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

versuche das: (es wurde nicht getestet)

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