title: Finding missing number using binary search
body: <p>I am reading book on programming pearls.</p>
  
  <blockquote>
    <p>Question: Given a sequential file that contains at most four billion
    32 bit integers in random order, find a 32-bit integer that isn't in
    the file (and there must be at least one missing). This problem has to
    be solved if we have a few hundred bytes of main memory and several
    sequential files.</p>
    
    <p>Solution: To set this up as a binary search we have to define a range,
    a representation for the elements within the range, and a probing
    method to determine which half of a range holds the missing integer.
    How do we do this?</p>
    
    <p>We'll use as the range a sequence of integers known to contain atleast
    one missing element, and we'll represent the range by a file
    containing all the integers in it. The insight is that we can probe a
    range by counting the elements above and below its midpoint: either
    the upper or the lower range has atmost half elements in the total
    range. Because the total range has a missing element, the smaller half
    must also have a mising element. These are most ingredients of a
    binary search algorithm for above problem.</p>
  </blockquote>
  
  <p>Above text is copy right of Jon Bently from programming pearls book.</p>
  
  <p>Some info is provided at following link</p>
  
  <p><a href="https://stackoverflow.com/questions/5011589/programming-pearls-binary-search-help">&quot;Programming Pearls&quot; binary search help</a></p>
  
  <p>How do we search by passes using binary search and also not followed with the example given in above link? Please help me understand logic with just 5 integers rather than million integers to understand logic.</p>