Write an algorithm to find an integer in an array. Given an array $A$ of integers, find an integer $k$ that is not present in $A$. Assume that the integers are $64$-bit unsigned integers, and typical laptop memory size; the size of $A$ is not known. Try to make your algorithm as efficient as possible.
The problem is that if I use a simple algorithm that checks every element A I have to check every element of A <=(FFFF,FFFF,FFFF,FFFF)h times and that is big load to a typical Laptop(PC). 
I don't understand what are all details for! 
This is an admission test question at Uni. 
Thanks for your help !
 A: Naive - Try all integers
There's the naive algorithm that just tries all integers one by one and then checks that it's not in the array. It takes $O(kn)$ times and $O(1)$ additional space (where $n$ is the size of the array, $k$ is the smallest integer not in the array).
Set - Build a set of all present integers and then look for an element that's missing
You could also build a set using Discrete Interval Encoding (see this, implemented in OCaml here) Trees (a variant of binary search trees where if $i,i+1,\dots,j$ are all in your set, you remember it as an interval instead of many elements. More precisely, it's a binary search tree containing maximal intervals contained in your set). Then, finding an element not inside is easy: it's either the min of the leftmost node minus one, or the max of the rightmost node plus one (or neither if your set contains everything in which case the tree will be a single interval [min_int, max_int]). You would get $O(n\log n)$ time and $O(n)$ space. (This would also work with binary search trees but you would have to do an additional $O(n)$ traversal of the tree, which wouldn't change the complexity)
Set - Same as previous but the set is represented as a sorted array without duplicates to do it in place
Or you could simply sort the array, remove duplicates and then return the first $i$ so that $A[i]\not = i$. That would be $O(n \log n)$ time and $O(1)$ additional space (but you destroyed the input, if you copy the array to keep the original input, it's $O(n)$ space).
Divide and conquer - Dichotomy on the possible integers by counting the number of integers bigger that the middlepoint
And then, there's the divide and conquer approach. The idea is that you start with $max=int\_max$ and $min=int\_min$ and then, you take $mid=\frac{min+max}{2}$. If there is a number missing in $[min,max]$, then either there is one missing in $[min,mid[$ or there is one missing in $[mid,max]$. So you count the number of numbers lower than $mid$ in $A$. If it's exactly $|[min,mid[|=mid-min$, you set $min=mid$ and otherwise, you set $max = mid-1$. The invariant that proves correction is that there is always an integer missing in $[min,max]$. And since the size of the interval is divided by two at each step, the total time complexity is $O(nb^2)$ where $b$ is the number of bits representing your integers (so in your case, $b=64$ so it's $O(n)$) and the space complexity is $O(1)$.
Remark: in the other complexities, I implicitly assumed that comparing two integers was $O(1)$ but you could also add a $b$ factor everywhere to get the complexities when $b$ is not $O(1)$.

The memory assumption probably tells you that you don't want to use too much extra memory (i.e. not $O(n)$ extra memory).
The 64-bits assumption tells you that the last algorithm is good because $b$ will not be big.
