Find in an array the next value greater than a pre-defined value

Question

Find in an array the next value greater than a pre-defined value

Navigation

#1 by (0 votes)

3

I have the following array with forech defined:

$getdepth = '{"result":"true","asks":[[20,13],[34,20],[30,8],[35,8],[4,40],"bids":[["18",22],["16",74],["70",99],["65",18],["1",15]]}';
$depth = json_decode($getdepth, true);
foreach ($depth['asks'] as $k_asks => $v_asks) {
$array_asks[$k_asks] = $v_asks[0];}

I wanted to know how to do a function to find the next value in "asks" greater than "30". Analyzing visually, the solution is 34.

Note: Value-to-value testing would be a solution, but the original array contains more than 2000 values, which makes the comparison impractical due to high processing load.

php array value

asked by anonymous 05.04.2014 / 02:30

1 answer

How to get the result of the query separated by columns? How do I access the clipboard image from the browser?

score 0 · Accepted Answer

You'll hardly get a better solution than testing from value to value. A complete pass in the list is O(n) , and this is the limit you can reach - because in the worst case (ie the value you want does not exist or it is the last one to be tested) you will have to evaluate all the elements list at least once. Incidentally, if what you want is a "minimax" (ie the lowest value greater than 30 - and not the first in the list, in order, that is greater than 30 ) then you will have to give a full pass anyway (to make sure there's no lower value going forward).

If this is an isolated operation, unfortunately I have nothing better to suggest ... But if this is something you need to do over and over, then you can amortize the search time of one of the two ways below:

Sort the array once ( O(n*log(n)) ) and, for each search you make, use the binary search ( O(log(n)) ). For a single operation this will be slower ( > O(n) ), but for multiple operations it will be faster ( < O(m*n) , since m > log(n) was the constant factor).

Place your elements in a binary search tree (same order of solution complexity above).

The above solutions apply to the "minimax" case. In the other case, before applying the suggested solution create an array with the maximum values found up to each index:

[[20,13],      [34,20],      [30,8],      [35,8],      [4,40]     ]
[[20,[20,13]], [34,[34,20]], [34,[30,8]], [35,[35,8]], [35,[4,40]]]

And do this sort / search on it, instead of the original array.

P.S. Are you having performance problems in practice? 2000 elements does not seem to me to be too large to justify a more complex solution ...