title: Finding the most efficient data structure to create an index file
body: <p>I have a video file, which consists of many successive frames of binary data. Each frame has also a unique timestamp (which is NOT its sequential number in file, but rather a value, provided by the camera at the recording time). On the other hand, I've got an API function which retrieves that frame based on the sequential number of that frame. To make things a bit more complicated - I have a player, who is provided with the timestamp, and should get the binary data for that frame.</p>
  
  <p>Another sad thing here: timestamps are NOT sequential. They can be sequential, but it is not guaranteed, as a wraparound may occur around max unsigned short size.
  So a sequence of timestamps could be either 
  54567, 54568, ... , 65535, 65536 , ... or<br>
  54567, 54568, ..., 65535, 0, 1, ...</p>
  
  <p>So it might look like the following:</p>
  
  <pre><code>Frame 0
  timestamp 54567
  binary data
  ........
  Frame 1
  timestamp 54569
  binary data
  ........
  Frame 2
  timestamp 54579
  binary data
  .
  .
  .
  Frame n
  timestamp m
  binary data
  
  0 &lt;= n &lt;= 65536 (MAX_UNSIGNED_SHORT)
  0 &lt;= m &lt;= MAX_UNSIGNED_INT
  </code></pre>
  
  <p>The clip player API should be able to get the binary frame by the timestamp. However, internally, I can get the frame only by its frame sequential number. So if I am asked for timestamp <code>m</code>, I need to iterate over <code>n</code> frames, to find the frame with timestamp <code>m</code>.</p>
  
  <p>To optimize it, I chose to create an index file, which would give me a match between timestamp and the frame sequential number. And here is my question:</p>
  
  <p>Currently my index file is composed of binary pairs of size <code>2*sizeof(unsigned int)</code>, which contains timestamp and frame sequential number. Player later on creates from that file <code>stl map</code> with <code>key==timestamp</code>, <code>value==frame sequential number</code>. </p>
  
  <p>Is there any way to do it more efficiently? Should I create my index file as a dump of some data structure, so it could later be loaded into memory by the clip player while opening the clip, so I would have an O(1) access to frames? Do you have other suggestions? </p>
  
  <p>UPD:</p>
  
  <p>I have updated the names and requirements (timestamps are not necessarily sequential, and frames num bounded by MAX_UNSIGNED_SHORT value). Also wanted to thank everyone who already took the time and gave an answer. The interpolation search is an interesting idea, although I never tried it myself. I guess the question would be the delta between <code>O(1)</code> and <code>O(log log N)</code> in runtime.</p>