title: Finding smallest number >= x not present in the given sorted array
body: <p>I am having difficulty writing a modified binary search algorithm that returns the smallest number greater than or equal to X which is <strong>not</strong> present in the sorted array.</p>
  <p>For example, if the array is <code>{1,2,3,5,6}</code> and <code>x = 2</code> then answer is 4. Please guide me how to write the binary search for this. I have to answer this in O(log n) time for each x. Since I am taking this array as input which will initially take linear time, you may do some kind of preprocessing on the array initially if you want.</p>
  <p>x is also taken as input and may or may not be present in the array.</p>
  <p>The input array may have repeating elements.</p>
  <p>My input numbers can be in the range [0,10^9] and hence first putting all the missing values in the array is not feasible because of space constraints.</p>
  <p>Also, you can do preprocessing which takes O(n) time since you are taking the array as input in linear time. After that, there will be let us say 10^6 queries of X, which you have to answer, each in O(log n) time</p>