Encontre um valor correspondente ou mais próximo em uma matriz

Como posso pesquisar e encontrar, para um determinado valor de destino, o valor mais próximo em uma matriz?

Digamos que eu tenha esse array exemplar:

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

Por exemplo, quando eu procuro com o valor alvo 0, a function deve retornar 0; quando eu procurar com 3, ele retornará 5; quando eu procurar com 14, ele retornará 12.

Passe o número que você está procurando como o primeiro parâmetro e a matriz de números para o segundo:

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

Uma abordagem preguiçosa particular é fazer com que o PHP ordene o array pela distância até o número procurado:

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

Esta é a function de alto desempenho que eu escrevi para grandes matrizes ordenadas

Testado, o loop principal precisa de apenas 20 iterações para um array com 20000 elementos.

Por favor, note que o array tem que ser classificado (ascendente)!

 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 encontra o elemento mais próximo
  • ARRAY_NEAREST_LOWER encontra o elemento mais próximo que é LOWER
  • ARRAY_NEAREST_HIGHER encontra o elemento mais próximo que é HIGHER

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

Você pode simplesmente usar array_search para isso, ele retorna uma única chave, se houver muitas instâncias de sua pesquisa encontradas dentro da matriz, ela retornará a primeira que encontrar.

Citação do PHP :

Se agulha é encontrada no palheiro mais de uma vez, a primeira chave correspondente é retornada. Para retornar as chaves para todos os valores correspondentes, use array_keys () com o parâmetro opcional search_value.

Exemplo de uso:

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

Atualizar:

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

A implementação de Tim irá cortá-lo a maior parte do tempo. No entanto, para o desempenho cauteloso, você pode classificar a lista antes da iteração e interromper a pesquisa quando a próxima diferença for maior que a última.

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

Para pesquisar o valor mais próximo em uma matriz de objects, você pode usar este código adaptado da resposta 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; } 

Isso deve te dar o que você precisa.

Considerando que a matriz de input é classificada em ordem crescente asort() por exemplo, você será muito mais rápido para pesquisar usando uma pesquisa dicotômica .

Aqui está uma adaptação rápida e suja de algum código que estou usando para inserir um novo evento em uma lista de events Iterable classificada por objects DateTime…

Assim, este código retornará o ponto mais próximo à esquerda (antes / menor).

Se você gostaria de encontrar o ponto matematicamente mais próximo: considere comparar a distância do valor de busca com o valor de retorno e o ponto imediatamente à direita (próximo) do valor de retorno (se existir).

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

tente isto: (não foi testado)

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