title: Which search data structure works best for sorted integer data?
body: <p>I have a sorted integers of over a billion, which data structure do you think can exploited the sorted behavior? Main goal is to search items faster... <br>
  Options I can think of -- <br>
  1) regular Binary Search trees with recursively splitting in the middle approach.<br>
  2) Any other balanced Binary search trees should work well, but does not exploit the sorted heuristics..</p>
  
  <p>Thanks in advance..</p>
  
  <p>[Edit]<br>
  Insertions and deletions are very rare...<br>
  Also, apart from integers I have to store some other information in the nodes, I think plain arrays cant do that unless it is a list right?</p>