title: Find a missing 32bit integer among a unsorted array containing at most 4 billion ints
body: <p>This is the <a href="http://books.google.com/books?id=kse_7qbWbjsC&amp;pg=PA11&amp;lpg=PA11&amp;dq=programming+pearls+column+2&amp;source=bl&amp;ots=DfwWCLDSbq&amp;sig=lHh50XmLgBT6AOUqxIz-Ao3HDxE&amp;hl=en&amp;ei=ZF3pSoP_LJjq6AP5463hCw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=8&amp;ved=0CCUQ6AEwBw#v=onepage&amp;q=programming%20pearls%20column%202&amp;f=false" rel="nofollow noreferrer">problem</a> described in <code>Programming pearls</code>. I can not understand binary search method descrbied by the author. Can any one helps to elaborate? Thanks.</p>
  
  <p>EDIT:
  I can understand binary search in general. I just can not understand how to apply binary search in this special case. How to decide the missing number is in or not in some range so that we can choose another. English is not my native language, that is one reason I can not understand the author well. So, use plain english please:)</p>
  
  <p>EDIT: Thank you all for your great answer and comments ! The most important lesson I leant from solving this question is <strong>Binary search applies not only on sorted array</strong>!</p>