.net - The quickest way to find an integer in sorted range data -

this question has answer here:

• fastest way search number in list of ranges 5 answers

i have sorted data has starting , ending integers of each range, , contiguous. data might this:

number start end  0      0     47  1      48    94  2      95    287  3      288   1123 

and on.

i integer 113 , want fastest way search data find matching number. can afford stick data structure optimizes retrieval / comparison speed.

my data large.

edit: chose answer, , code ended with:

  public function endingcapturenumber(captureend integer) integer     endingcapturenumber = captureends.binarysearch(captureend)     if endingcapturenumber < 0       return (not endingcapturenumber) - 1     end if   end function 

capture ends list of end of each range. not bitwise compliment. since finds first greater, subtract 1 last not greater.

edit: duplicate question rebuttal

the answer came out of uses built in binarysearch handles values not exact match. seekers reading other article not learn (imho) better answer. plus, other question cluttered actual data types op used in rl problem.

stick binary search. if have n ranges , k numbers, searching take o(klogn).

using @steve wellens's suggestion of spreading take lot of setup - o(r) (with r being last range ending - 1123 in example). after setup, k searches take o(k), you're looking @ o(k+r)

now, if maximum number less klogn, , memory not problem, spread out ranges. if not (which guess, said had lot of data), binary search faster.