Search array for closest key match

Question

Is there a better / more elegant / more efficient way of doing this?

I have an array that I'm searching the keys for a value that either matches or is the greatest value that is less than the search value. Hope that makes sense.

My current method is a bit of a brute force attempt that is fine for a small collection of data but this function will need to run many times with a large array.

$needle = '2013-04-04';    

$haystack = array    (
                     '2013-01-01'   => 1,
                     '2013-04-03'   => 2,
                     '2013-04-05'   => 3,
                     '2013-07-23'   => 4,
                     '2013-09-12'   => 5,
                     '2013-10-18'   => 6,
                     '2013-11-01'   => 7
                     );

krsort($haystack);

foreach ($haystack as $k => $v)
    {
    $possibleMatch = $k;
    if ($needle >= $k) break;
    }

return $possibleMatch

Thanks in advance

If the array is sorted, or can be sorted, use binary search. Either way, think in terms of finding the largest key that is less than or equal to the probe. — Patricia Shanahan, Feb 22 '14 at 12:49
Not initially, but it can be. Its retrieved from a mysql database. — Gavin, Feb 22 '14 at 12:49
@Gavin Will the array be used for other purposes, or would just finding the correct row using SQL be an option? — Joachim Isaksson, Feb 22 '14 at 12:55
The array will be used many times so I thought it would be more efficient to store all data in an array and search the array rather than hitting the database 1000s of times. — Gavin, Feb 22 '14 at 13:00

greg0ire · Answer 1 · 2014-02-22T13:04:10.593

Looking at your data, it looks like your array is sorted. If it is not, stay with brute force. I think a fast way to get your result if there is no exact match is a bisection (also called binary search or dichotomy). Pseudo code :

Take a key in the middle of your array. If the key is inferior to your search, search in the sub-array that starts with this key If the key is superior to your search, search in the sub-array that ends with this key Repeat until the array is of size 1.

Like this :

  +----------------------------------------------------------------------------------------+
  |                                                                                        |
  +----------------------------------------------------------------------------------------+
  +----------------------------------------+ +---------------------------------------------+
  |                                        | |                                             |
  +----------------------------------------+ +---------------------------------------------+
  +------------------+ +-------------------+
  |                  | |                   |
  +------------------+ +-------------------+
                       +--------+ +--------+
                       |        | |        |
                       +--------+ +--------+
                       +---++---+
                       |   ||   |
                       +---++---+
                       +-+
                       | |
                       +-+

                      desired value

Warning : DO NOT, I repeat, DO NOT search for bisection on google images. It hurts.

score 0 · Answer 2 · edited May 23 '17 at 12:20

0

Use a modified binary search. One sample is here - modify binary search to find the next bigger item than the key; can be easily customized to suit your needs.

edited May 23 '17 at 12:20

Community

1
1

answered Feb 22 '14 at 12:52

Amit

1,836
15
24

Search array for closest key match

2 Answers2