-
-
Save javafun/fed2b5446a14ad54310e8e4a9acf62a3 to your computer and use it in GitHub Desktop.
Finds the 'nearest value' of a needle in a SORTED numeric array (ascending). Via https://stackoverflow.com/a/22375510/237739
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/** | |
* Class NearestValue | |
* Finds the 'nearest value' of a needle in a SORTED numeric array (ascending) | |
* Via https://stackoverflow.com/a/22375510/237739 | |
* | |
* Usage: | |
* $array = [1000,2000,3000,4000,5000]; | |
* $needle = 1337; | |
* $nearestValue = NearestValue::array_numeric_sorted_nearest($array, $needle); | |
*/ | |
class NearestValue { | |
private static $ARRAY_NEAREST_DEFAULT = 0; | |
private static $ARRAY_NEAREST_LOWER = 1; | |
private static $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 | |
*/ | |
public static function array_numeric_sorted_nearest($array, $value, $method=0) { | |
$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] ?? null; | |
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] ?? null; | |
$next_key = $array[$index + 1] ?? null; | |
switch($method) { | |
default: | |
case self::$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 self::$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 self::$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]; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment