Finding an element in infinite sorted array

I am not sure if I understand your problem well, but would not that be a bit easier:

1. Check if a[i] > x for i=1,2,4,8,16… Do not search until a[i]=+infinity, it’s IMO unneccessary
2. When found, do binary search between a[previous i] and a[i], not between a[1] and a[i]. However this saves only one step of binary search, so rather is not that much of optimalization

Find next greater number with same set of digits

534976
1. search from right side, and stop where a digit is less than succeeding element(4 < 9)
2. swap that digit wrt last digit(536974)
3. order all the digits in ascending after the selected digit(4 in this case,974 falls after 4) result : 536479

http://www.geeksforgeeks.org/find-next-greater-number-set-digits/