| 1 |
|
| 2 |
|
| 3 | #-----------------------------------------------------------------------------------------------------------
|
| 4 | module.exports = binary_interval_search = ( data, lo_bound_key, hi_bound_key, id_key, probe ) ->
|
| 5 | ### Given `data`, three indexes, and a `probe`, perform a binary search through `data` to find into which
|
| 6 | of the given intervals `probe` falls.
|
| 7 |
|
| 8 | `data` must be a list of lists or objects with each entry representing an interval; intervals must not
|
| 9 | overlap, and the intervals in `data` must be sorted in ascending ordered. There may be gaps between
|
| 10 | intervals.
|
| 11 |
|
| 12 | You must give the keys to the lower and upper boundaries, so that `data[ idx ][ lo_bound_key ]` yields the
|
| 13 | first value and `data[ idx ][ hi_bound_key ]` the last value of each interval. `id_key` should be either
|
| 14 | `null` or a key for an entry so that `data[ idx ][ id_key ]` yields the ID (or whatever info) you want to
|
| 15 | retrieve with your search.
|
| 16 |
|
| 17 | If a match is found, the result will be either the index of the matching interval, or, if `id_key` was
|
| 18 | defined, `interval[ id_key ]`. If no match is found, `null` is returned.
|
| 19 |
|
| 20 | With thx to http://googleresearch.blogspot.de/2006/06/extra-extra-read-all-about-it-nearly.html
|
| 21 | ###
|
| 22 | lo_idx = 0
|
| 23 | hi_idx = data.length - 1
|
| 24 | #.........................................................................................................
|
| 25 | while lo_idx <= hi_idx
|
| 26 | mid_idx = Math.floor ( lo_idx + hi_idx ) / 2
|
| 27 | id_and_range = data[ mid_idx ]
|
| 28 | lo_bound = id_and_range[ lo_bound_key ]
|
| 29 | hi_bound = id_and_range[ hi_bound_key ]
|
| 30 | #.......................................................................................................
|
| 31 | if lo_bound <= probe <= hi_bound
|
| 32 | return if id_key? then id_and_range[ id_key ] else mid_idx
|
| 33 | #.......................................................................................................
|
| 34 | if probe < lo_bound then hi_idx = mid_idx - 1 else lo_idx = mid_idx + 1
|
| 35 | #.........................................................................................................
|
| 36 | return null
|
| 37 |
|